Hdu 5738 Eureka （组合数中档题）

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5738
题目大意：
给定n个点，$(n<=1000)$，其中共线的点可加入同一个集合，集合中至少有两个元素，重点与任何点（包括本身）可视作共线，求有多少个这样的集合？
分析：
首先要得到所有共线的点，同时判重也是个问题，显而易见需要对点排序，一般是按x坐标从小到大，x坐标相同y坐标从小到大，然后遍历每一个点对

for (int i = 1 ; i <= n ; i ++)
{
    for (int j = i + 1 ; j <= n ; j ++)
    {
    }
}

对每个点对得到一个斜率，斜率使用分数形式存在结构体中，创建分数到出现次数的映射，$map<fen , int >$分数需要最简形式，同时特判，如果分子分母同时为0，当前点重点的计数+1，最后得到与当前点重合的点的个数，然后计算当前点的总集合数，首先当前点（$Point{\space}i$）必取，然后任意一点与他均共线，从与它不重合的所有点中取，若有n个点与当前点共一线，则取法数为$C_n^1+C_n^2+C_n^3+{\cdots}+C_n^n = 2^n-1$,但是还要考虑重点，假设有m个重点，在所有集合中，重点均可取$0,1,2,3{\cdots},m$个，即取法种数为$C_0^m+C_1^m+C_2^m+C_3^m+{\cdots}+C_{m-1}^m+C_m^m = 2^m$，总的集合数即为$2^m*(2^n-1)$种，遍历集合同时取模即可，最后记得加上只选重点时的集合数，即为$2^m-1$种，数据应该会爆$int$，复杂度$O(n^2lgn)$。

代码（代码略长，多校时临场写的）：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<map>
#include<deque>
#include<cmath>
#include<algorithm>

using namespace std;
long long MODA = 1e9 + 7;
const int MAXN = 200050;

inline void print(char pt) {
    printf("%c\n", pt);
}
inline void print(int pt) {
    printf("%d\n", pt);
}
inline void print(long long pt) {
    printf("%I64d\n", pt);
}
inline void print(double pt) {
    printf("%.20f\n", pt);
}
inline void print(char pt[]) {
    printf("%s\n", pt);
}
inline void print() {
    printf("\n");
}
inline void scan(int &pt) {
    scanf("%d", &pt);
}
inline void scan(char &pt) {
    scanf("%c", &pt);
}
inline void scan(long long &pt) {
    scanf("%I64d", &pt);
}
inline void scan(double &pt) {
    scanf("%lf", &pt);
}
inline void scan(char pt[]) {
    scanf("%s", pt);
}
struct pii {
    long long a;
    long long b;
    friend int operator<(pii a, pii b) {
        if (a.a != b.a)
            return a.a < b.a;
        return a.b < b.b;
    }
};

struct str {
    char val[1005];
    str() {
        memset(val, 0, sizeof(val));
    }
    friend int operator<(str a, str b) {
        return strcmp(a.val, b.val) < 0;
    }
};

long long gcd(long long x, long long y) {
    return y ? gcd(y, x % y) : x;
}
long long lcm(long long x, long long y) {
    return x * (y / gcd(x, y));
}

int bits[50];
void getbits() {
    for (int i = 0; i < 30; i++) {
        bits[i] = 1 << i;
    }
}

long long Q_pow(long long x, long long y) {
    long long res = 1;
    while (y) {
        if (y % 2 == 1) {
            res *= x;
            res %= MODA;
        }
        x = x * x;
        x %= MODA;
//        if(x<=1e-5){
//            return 0;
//        }
        y /= 2;
    }
    return res;
}

//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
long long extend_gcd(long long a, long long b, long long &x, long long &y) {
    if (a == 0 && b == 0)
        return -1; //无最大公约数
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extend_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
//*********求逆元素*******************
//ax = 1(mod n)
long long mod_reverse(long long a, long long MOD) {
    long long x, y;
    long long d = extend_gcd(a, MOD, x, y);
    if (d == 1)
        return (x % MOD + MOD) % MOD;
    else
        return -1;
}


struct point {
    long long x, y;
    friend int operator<(const point &a, const point &b) {
        if (a.x != b.x)
            return a.x < b.x;
        return a.y < b.y;
    }

    friend int operator==(const point &a, const point &b) {
        return (a.x == b.x) && (a.y == b.y);
    }
};

struct fenshu {
    long long fenzi, fenmu;
    void zhengqi() {
        if (fenzi == 0 && fenmu == 0) {

        } else if (fenzi == 0) {
            fenmu = 1;
        } else if (fenmu == 0) {
            fenzi = 1;
        } else {
            if (fenmu < 0) {
                fenzi = -fenzi;
                fenmu = -fenmu;
            }
            int flag0 = (fenzi < 0);
            if (flag0) {
                fenzi = -fenzi;
            }
            int nowgcd = gcd(fenzi, fenmu);
            fenzi /= nowgcd;
            fenmu /= nowgcd;
            if (flag0) {
                fenzi = -fenzi;
            }
        }
    }
    friend int operator<(const fenshu &a, const fenshu &b) {
        if (a.fenzi != b.fenzi)
            return a.fenzi < b.fenzi;
        return a.fenmu < b.fenmu;
    }

};

int h, n, m, w;
point a[100050];
int endof[100050];
long long pow2[1050];

map<fenshu, int> mapfenshu;
int main() {
    long long ti = 1;
    for (int i = 0; i < 1050; i++) {
        pow2[i] = ti;
        ti *= 2;
        ti %= MODA;
    }

    int T;
    scan(T);
    while (T--) {
        scan(n);
        for (int i = 0; i < n; i++) {
            scan(a[i].x);
            scan(a[i].y);
        }
        sort(a, a + n);
        endof[n - 1] = n - 1;
        for (int i = n - 2; i >= 0; i--) {
            if (a[i + 1] == a[i]) {
                endof[i] = endof[i + 1];
            } else {
                endof[i] = i;
            }
        }

        long long ansa = 0;
        for (int i = 0; i < n; i++) {
            int chongdian = endof[i] - i;
            mapfenshu.clear();
            for (int j = endof[i] + 1; j < n; j++) {

                fenshu newf;
                newf.fenmu = a[j].x - a[i].x;
                newf.fenzi = a[j].y - a[i].y;
                newf.zhengqi();
                mapfenshu[newf]++;
            }

            for (auto au : mapfenshu) {
                ansa += (pow2[chongdian]) * (pow2[au.second] - 1);
                if (ansa < 0)
                    ansa += MODA;
                ansa %= MODA;
            }
            ansa += pow2[chongdian] - 1;
            if (ansa < 0)
                ansa += MODA;
            ansa %= MODA;
        }
        print(ansa);
    }
    return 0;
}