my outputs are correct. i think
anyone give me advice to solve this problem.
here my code.
Code: Select all
#include "stdio.h"
#include "stdlib.h"
#define SIZE 10050
typedef struct Gas
{
int start;
int end;
bool isRemoved;
}Gas;
int cmp(const void* a, const void* b)
{
if(((Gas*)a)->start == ((Gas*)b)->start)
return ((Gas*)a)->end - ((Gas*)b)->end;
return ((Gas*)a)->start - ((Gas*)b)->start;
}
int MIN(int a, int b)
{
return (a<=b)?a:b;
}
int MAX(int a, int b)
{
return (a>=b)?a:b;
}
int main()
{
Gas gas[SIZE];
int length, number, location, range, max, cnt;
int sRange, eRange;
bool exit;
while(1)
{
scanf("%d %d", &length, &number);
if(length == 0 && number == 0)
break;
max = -1000000;
cnt = 0;
exit = false;
for(int i=0; i<number; i++)
{
scanf("%d %d", &location, &range);
gas[i].start = location - range;
gas[i].end = location + range;
gas[i].isRemoved = false;
}
qsort(gas, number, sizeof(Gas), cmp);
if(gas[0].start > 0)
{
puts("-1");
continue;
}
max = gas[0].end;
if(max >= length)
{
printf("%d\n", number-1);
continue;
}
for(int i=1; i<number; i++)
{
if(max >= gas[i].start)
{
max = MAX(max, gas[i].end);
if(max >= length)
break;
}
}
if(max < length)
{
puts("-1");
continue;
}
for(int i=0; i<number-1; i++)
{
if(exit)
break;
if(!gas[i].isRemoved && gas[i].start <= 0 && gas[i].end >= length)
{
cnt = number-1;
exit = true;
break;
}
for(int j=i+1; j<number; j++)
{
if(!gas[i].isRemoved && gas[i].end >= gas[j].start)
{
sRange = MIN(gas[i].start, gas[j].start);
eRange = MAX(gas[i].end, gas[j].end);
if(sRange <= 0 && eRange >= length)
{
cnt = number-2;
exit = true;
break;
}
for(int k=i+1; k<j; k++)
{
if(!gas[k].isRemoved && sRange <= gas[k].start && gas[k].end <= eRange)
{
if(gas[k].start == 0 && gas[k].end >= gas[i].end)
break;
cnt++;
gas[k].isRemoved = true;
}
}
if(sRange <= 0)
{
for(int z=0; z<i; z++)
{
if(gas[z].end < eRange)
{
cnt++;
gas[z].isRemoved = true;
}
}
}
if(eRange >= length)
{
cnt += number - j -1;
exit = true;
break;
}
}
}
}
printf("%d\n", cnt);
}
return 0;
}