poj1828

题意：平面上的一些点，问有多少点的右上方没有点（即不存在x，y均比它大的点）。

分析：本来想 用求逆序数的方法，后来上网发现了更简单的方法。

按x从小到大，x相等按y从小到大排序后，从右到左，一旦遇到一个比之前见过的y都大的y，就把ans++；

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
usingnamespace std;

#define maxn 50005

struct Point
{
    int x, y;
}point[maxn];

int n;

void input()
{
    for (int i =0; i < n; i++)
        scanf("%d%d", &point[i].x, &point[i].y);
}

booloperator< (const Point &a, const Point &b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

void work()
{
    int ans =1;
    int maxy = point[n -1].y;
    for (int i = n -2; i >=0; i--)
    {
        if (point[i].y > maxy)
        {
            ans++;
            maxy = point[i].y;
        }
    }
    printf("%d\n", ans);
}

int main()
{
    //freopen("t.txt", "r", stdin);
while (scanf("%d", &n), n)
    {
        input();
        sort(point, point + n);
        work();
    }
    return0;
}