2016 Multi-University Training Contest 2

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

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

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

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

考虑到有重复点的情况,我的做法是记录重复点的个数 NumiNum_i,然后当成一个点遍历,计算答案时首先加上 2NumiNumi12 ^ {Num_i} - Num_i - 1(这个实际上是至少有两个元素的子集的个数),然后如果有共线的情况,假设和 mm 个点共线,那么实际上答案需要加上 (2Numi1)(2m1)(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;
}
更新于 阅读次数