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