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;
}