INFOMAN брой 20

/*
3
6 3
1 3
2 5

XVII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА

Втори ден - Задача 2. Покритие

Дадени са N (0 < N < 100) отсечки върху една права. Всяка 
отсечка е зададена с координатите на двата си края ai и bi,  
i = 1, ..., N. Тези координати са цели числа от интервала 
(-999, 999). Някои от отсечките могат да бъдат пресичащи 
се. Напишете програма COVER.EXE, която премахва минимален 
брой от дадените отсечки така, че никои две от останалите 
отсечки да нямат обща вътрешна точка, т.е. точка, която 
принадлежи едновременно и на двете отсечки и е вътрешна за 
поне едната от тях.

Входните данни се четат от текстов файла COVER.INP. В 
първия ред на файла е записано цялото число N. Следват N 
на брой реда, всеки съдържащ по две цели числа, разделени с 
една шпация. Всяка двойки от тези числа задава координатите 
на двата края на поредната от дадените отсечки.

Резултатът от програмата трябва да бъде записан в текстовия 
файл COVER.OUT. В първия ред на файла трябва да е записано 
едно цяло число, равно на броя отсечките,  които са останали, 
след като програмата е премахнала тези, за които това се 
изисква от условието на задачата. Във всеки един от 
следващите редове на файла трябва да са записани координати 
на левия и на десния край на поредната от отсечките, които 
са останали. Тези две координати трябва да са разделени с една 
шпация. Координати на левите краища трябва да са изведени по 
редовете на файла в нарастващия си ред. Ако задачата допуска 
няколко решения, вашата програма трябва да отпечата само едно 
от тях, без значение кое.     

РЕШЕНИЕ:

Това е стандартно динамично решение. Подреждаме ги по дясна точка. Записваме
в текущото решение първата отсечка. После за всяка следваща проверяваме дали
се застъпва с някоя отсечка от текущото решение и ако не се застъпва я добавяме
към решението.

Защо това решение е най-добро? Защото във всеки един междинен момент всяко решение
се характеризира с две величини от които зависи по-нататъшното развитие на решението -
колко отсечки сме използвали и до коя точка сме стигнали (коя е най-дясната точка
в решението). Във всеки един момент най-доброто решение е това в което сме взели 
максимален брой отсечки и най-дясната ни точка е колкото се може по-вляво. Описаният
по-горе (и реализиран по-долу) алгоритъм ни дава точно такъв подбор на точките.


Velin Tzanov
*/

#include <stdio.h>

FILE *fn;
int n;
int o1[101][2];
int o2[101][2];
int best;
int sol[101];

void main(void) {
int i, j, t1, t2;

char sTemp[200]; fn=fopen("cover.c", "r"); fgets(sTemp,200,fn); // fn=fopen("COVER.INP", "r");
fscanf(fn, "%d", &n);
for (i=0; i<n; i++) {
  fscanf(fn, "%d %d", &o1[i][0], &o1[i][1]);
  if (o1[i][1] < o1[i][0]) {
    t1=o1[i][1];
    o1[i][1]=o1[i][0];
    o1[i][0]=t1;
  }
}
fclose(fn);

for (i=0; i<n; i++) {
  t1=1000;
  t2=n;
  for (j=0; j<n; j++) {
    if (o1[j][1] < t1) {
      t2=j;
      t1=o1[j][1];
    }
  }
  o2[i][0]=o1[t2][0];
  o2[i][1]=o1[t2][1];
  o1[t2][1]=1000;
}

for (i=0; i<n; i++) {
  for (j=0; j<best; j++) {
    if (o2[i][0] < o2[sol[j]][1]) break;
  }
  if (j==best) {
    sol[best]=i;
    best++;
  }
}

fn = stdout; // fn=fopen("COVER.OUT", "w");
fprintf(fn, "%d\n", best);
for (i=0; i<best; i++) fprintf(fn, "%d %d\n", o2[sol[i]][0], o2[sol[i]][1]);
fclose(fn);

}