d555: 平面上的極大點

#include<bits/stdc++.h>

using namespace std;

struct dot {

	int x, y;

} dots[500000];

bool Cmp(dot a, dot b) {

	if (a.x != b.x)

		return a.x > b.x;

	return a.y > b.y;

}

int main() {

	cin.sync_with_stdio(false), cin.tie(0);

	int n, tcnt = 1, cnt, now, y;

	bool p[500000] = {};

	while (cin >> n) {

		cnt = now = 0;

		for (int i = 0; i < n; i++)

			cin >> dots[i].x >> dots[i].y, p[i] = false;

		sort(dots, dots + n, Cmp), now = 0, y = -1;

		for(int i = 1; i < n; i++)

			if (dots[now].x != dots[i].x) {

				if (dots[now].y > y)

					p[now] = true, y = dots[now].y, cnt++;

				now = i;

			}

		if (dots[now].y > y)

			p[now] = true, cnt++;

		cout << "Case " << tcnt << ":\n", tcnt++;

		cout << "Dominate Point: " << cnt << '\n';

		for (int i = n - 1; i >= 0; i--)

			if (p[i])

				cout << '(' << dots[i].x << ',' << dots[i].y << ")\n";

	}

}