ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1112. Покрытие

Can you help me?
Послано Nike_1 3 дек 2010 12:40
My english ability is very poor!So I can't express correctly~I feel very sorry.
    About this problem,I have tried many data.But I am sorry I can't found that anything is wrong.Next I will give my code,I hope somebody can help me,or give me some hints.Thank you very much~
#include "stdio.h"
#include "malloc.h"
int main()
{
  int amount,i,j;
  int **endpoint;
  int *flag,temp;
  int max,index = -1;
  int condition = 0,count = 0;
  int test = 0;
  scanf("%d",&amount);
//  if(amount <= 0 || amount >= 100)
//  {
 //   return 0;
 // }
  endpoint = (int **)malloc(sizeof(int*) * amount);
  flag = (int *)malloc(sizeof(int) * amount);
  for( i = 0;i < amount;i ++)
  {
    endpoint[i] = (int *)malloc(sizeof(int) * 2);
  }
  flag = (int *)malloc(sizeof(int) * amount);
  for( i = 0;i < amount;i ++ )
  {
    scanf("%d%d",&endpoint[i][0],&endpoint[i][1]);
    if( endpoint[i][0] == endpoint[i][1] || endpoint[i][0] > 999 || endpoint[i][0] < -999 || endpoint[i][1] > 999 || endpoint[i][1] < -999)
    {
       return 0;
    }
    flag[i] = 0;
     if(endpoint[i][0] > endpoint[i][1])
     {
         temp = endpoint[i][0];
         endpoint[i][0] = endpoint[i][1];
         endpoint[i][1] = temp;
     }
  }
  //排序
  for(i = 0; i < amount - 1 ;i ++)
  {
      for(j = i + 1;j < amount;j++)
      {
         if(endpoint[i][0] > endpoint[j][0])
         {
           temp = endpoint[i][0];
           endpoint[i][0] = endpoint[j][0];
           endpoint[j][0] = temp;
           temp = endpoint[i][1];
           endpoint[i][1] = endpoint[j][1];
           endpoint[j][1] = temp;
         }
      }
  }
  while(condition != 0 || count == 0 )
  {
      condition = 0;
      test = 0;
   for(i = 0;i < amount;i ++)
   {
   if(endpoint[i][0] !=0 || endpoint[i][1] != 0)
     {
     for(j = 0;j < amount;j ++)
     {
       if(endpoint[j][0] !=0 || endpoint[j][1] != 0)
       {
        if(endpoint[i][0] > endpoint[j][0] && endpoint[i][0] < endpoint[j][1] )
        {
         flag[i] += 1;
       }
       else if(endpoint[i][0] <= endpoint[j][0] && endpoint[i][1] >= endpoint[j][1] )
       {
           if(i != j && ( endpoint[i][0] != 0 || endpoint[j][0] != 0 ))
             flag[i] += 1;
       }
       else
       {
         if(endpoint[i][1] > endpoint[j][0] && endpoint[i][1] < endpoint[j][1])
         {
           flag[i] += 1;
         }
       }
      }
     }
    }
  }
  max = flag[0];
  index = 0;
  condition += flag[0];
  flag[0] = 0;
  for( i = 1 ;i < amount;i ++ )
  {
      condition += flag[i];
    if(max < flag[i])
    {
        max = flag[i];
        index = i;
    }
    flag[i] = 0;
  }
    if(index != -1 && condition != 0 )
    {
       endpoint[index][0] = 0;
       endpoint[index][1] = 0;
    }
    count ++;
 }
  printf("%d\n",amount - count + 1);
  for(i = 0 ;i < amount;i ++)
  {
      if(endpoint[i][0] != 0 || endpoint[i][1] != 0)
      {
         printf("%d %d\n",endpoint[i][0],endpoint[i][1]);
      }
  }
  return 0;
}