HDOJ 5738 Eureka 数学原理

给出平面上的n个点，每个点有唯一的标号（label），这n个标号的集合记作S，点可能重合。求满足下列条件的S的子集T

的数目：

1. |T|≥2

2.T中的点共线

这个题的重点落在了：

一：如何处理重复的点？

二：如何判断共线？

判断重复，算是比较简单：把所有的点排序，先按x升序，再按y升序，就方便判断点的重合了

如何判断共线呢？

采用斜率！斜率用（x，y）来表示，先化归成不可约

那么需要对相同的斜率的进行计算和排重

看了各位大神的题解之后，采用

map<pair<long long,long long>,int> vis;
map<pair<long long,long long>,int>::iterator it;

pair这个是斜率

后面的int呢，就是出现了多少次

所以我们可以枚举每一个点

然后看之后的点，有多少个与它相同，有多少组点与其共线，那么用乘法原理，就能够计算出来

因为，每组的点，要么取，要么不取

重合的点数记为res（不算自己）

某一个斜率下有的点记为cnt
方案一：只选用重合的点，那么至少选1个，不能不选。所以方案数目为pow（2，res）-1

方案二：可以选用重合的点，至少选择一个非重合的点

那么用乘法原理，pow（2，res）*【pow（2，cnt）-1】

剩下的就是对不同的点，不同的斜率进行枚举

注意，可以提前打表把2的幂次打表好，不然容易超时的

#include<bits/stdc++.h>
using namespace std;

map<pair<long long,long long>,int> vis;
map<pair<long long,long long>,int>::iterator it;
const int mod=1e9+7;
const int maxn=1050;
int n,t;
struct node{
	long long x,y;
}num[maxn];
long long pow2[maxn];

bool cmp(node a,node b){
	if (a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}

/*
long long qpow(long long a,long long b){
	if (b<0) return 0;
	a%=mod;
	long long ans=1;
	while(b){
		if (b&1) ans=(ans*a)%mod;
		b>>=1;
		a=(a*a)%mod;
	}
	return ans;
}
*/

int main(){
	//freopen("input.txt","r",stdin);
	pow2[0]=1;
	for(int i=1;i<=1000;i++)
		pow2[i]=(pow2[i-1]*2)%mod;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%I64d%I64d",&num[i].x,&num[i].y);
		sort(num+1,num+n+1,cmp);
		long long ans=0;
		for(int i=1;i<=n;i++){
			vis.clear();
			int res=0;
			for(int j=i+1;j<=n;j++){
				if (num[j].x==num[i].x&&num[j].y==num[i].y) res++;
				else{
					long long dx=num[i].x-num[j].x;
					long long dy=num[i].y-num[j].y;
					long long GCD=__gcd(dx,dy);
					if (GCD){
						dx/=GCD;dy/=GCD;
					}
					vis[make_pair(dx,dy)]++;
				}
			}
			if (res>1){
				//ans+=(qpow(2,res-1)-1)%mod;
				ans+=(pow2[res]-1+mod)%mod;
				ans%=mod;
			}
			for(it=vis.begin();it!=vis.end();it++){
				long long cnt=(it->second);
				ans=(ans+((pow2[cnt]-1)*pow2[res])%mod)%mod;
			}
		}
		printf("%I64d\n",(ans+mod)%mod);
	}
	return 0;
}