poj兩個相似的題目,很有代表性。
pku 1828
pku 2726
題目大意是給出平面上的若干點,找出符合某種要求的點(x0, y0),如要求不存在點(x, y),使得x>=x0 且 y>=y0,換一種說法就是對任意點(x, y)都有x<x0 或 y<y0.
下面給出pku 1828的代碼
#include <stdlib.h>
#include <stdio.h>


struct node
{
int x,y;
}a[50001];

int cmp(const void *aa, const void *bb)


{
node* a=(node*)aa;
node* b=(node*)bb;
if(a->x==b->x) return a->y-b->y;
return a->x-b->x;
}

int i,j,k,n;

int main()


{
while(scanf("%d",&n) && n!=0)

{
for(i=0;i<n;i++) scanf("%d%d",&a[i].x, &a[i].y);
qsort(a,n,sizeof(node),cmp);
//for(i=0;i<n;i++) printf("%d %d\n",a[i].x,a[i].y);
int total=1;
int maxi=a[n-1].y;
for(i=n-2;i>=0;i--)

{
if(a[i].y>maxi)

{
maxi=a[i].y;
total++;
}
}
printf("%d\n",total);
}
return 1;
}