HDU 5738 Eureka

2016 Multi-University Training Contest 2

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5738

题目大意在经过简单的推理之后之后是：给你 $n$ 个平面上的点，求出所有共线点的集合 $S_i$ （要求集合尽可能大），答案是 $\sum_i{[2^{card(S_i)} - card(S_i) - 1]}$

最开始我的想法是，两两求出一条直线（用直线方程的三个常数作为直线特征值）扔到map里统计个数，然后再遍历一下map求解，然而map毕竟不是unordered_map所以T掉了（说不定unordered_map也会T）

正解是极角排序，但是需要先对每个点的坐标 $(x, y)$ 进行双关键字排序，这样从前往后枚举每一个点时，该点之后的点都在该点右边，这个时候其实答案的公式就要变一下，因为某个点与它右边的点组成的集合不一定是最大的，这个时候实际上我们在每个点上统计答案的时候，计算的是该点在集合中的子集的个数。

考虑到有重复点的情况，我的做法是记录重复点的个数 $Num_i$，然后当成一个点遍历，计算答案时首先加上 $2 ^ {Num_i} - Num_i - 1$（这个实际上是至少有两个元素的子集的个数），然后如果有共线的情况，假设和 $m$ 个点共线，那么实际上答案需要加上 $(2 ^ {Num_i} - 1) \cdot (2 ^ {m} - 1)$，（反正这些多YY一下都可以出来……

#include <map>
#include <cmath>
#include <cstdio>

#define MOD 1000000007
#define N 2000

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
map<PII, int>::iterator it;
map<PII, int> points;

struct point {
	 int x, y, num;
} a[N];

#define po const point &

int base;
inline LL xmul(po a, po b, po c) {
	return 1LL * (b.x - a.x) * (c.y - a.y)
		- 1LL * (b.y - a.y) * (c.x - a.x);
}
inline bool cmpByXY(po p, po q) {
	if (p.x == q.x)
		return p.y < q.y;
	return p.x < q.x;
}
inline bool cmpByAngle(po p, po q) {
	return xmul(a[base], p, q) > 0;
}

int t, n, x, y;
int bin[N];
LL dx, dy, cnt, ans;

LL absll(LL x) {
	return x > 0 ? x : -x;
}

LL gcd(LL a, LL b) {
	if (!(a | b)) return 1;
	if (a == 0) return absll(b);
	if (b == 0) return absll(a);
	return a % b ? gcd(b, a % b) : absll(b);
}

int main() {
	bin[0] = 1;
	for (int i = 1; i < N; i++)
		bin[i] = 2 * bin[i - 1] % MOD;
	for (int i = 0; i < N; i++)
		bin[i] += MOD - 1,
		bin[i] %= MOD;

	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		points.clear();
		while (n--) {
			scanf("%d%d", &x, &y);
			it = points.find(PII(x, y));
			if (it == points.end())
				points[PII(x, y)] = 1;
			else it->second++;
		}
		it = points.begin();
		for (n = 0; it != points.end(); it++) {
			a[n].x = it->first.first;
			a[n].y = it->first.second;
			a[n++].num = it->second;
		}
		ans = 0;
		for (int i = 0; i < n; i++) {
			base = i;
			sort(a + i + 1, a + n, cmpByAngle);
			dx = dy = cnt = 0;
			a[n] = a[i];
			if (a[i].num > 1) {
				ans += bin[a[i].num] + MOD - a[i].num;
				ans %= MOD;
			}
			for (int j = i + 1; j <= n; j++) {
				LL _x = a[j].x - a[i].x;
				LL _y = a[j].y - a[i].y;
				LL tmp = gcd(_x, _y);
				_x /= tmp; _y /= tmp;

				if (_x != dx || _y != dy) {
					ans += 1LL * bin[cnt] * bin[a[i].num];
					ans %= MOD;
					cnt = 0;
				}
				cnt += a[j].num;
				dx = _x; dy = _y;
			}
			sort(a + i + 1, a + n, cmpByXY);
		}
		printf("%lld\n", ans);
	}

	return 0;
}