首页 > 代码库 > hdu 5738 Eureka
hdu 5738 Eureka
Eureka
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2924 Accepted Submission(s): 816
Problem Description
Professor Zhang draws n points on the plane, which are conveniently labeled by 1,2,...,n. The i-th point is at (xi,yi). Professor Zhang wants to know the number of best sets. As the value could be very large, print it modulo 109+7.
A set P (P contains the label of the points) is called best set if and only if there are at least one best pair in P. Two numbers u and v (u,v∈P,u≠v) are called best pair, if for every w∈P, f(u,v)≥g(u,v,w), where f(u,v)=(xu−xv)2+(yu−yv)2−−−−−−−−−−−−−−−−−−√ and g(u,v,w)=f(u,v)+f(v,w)+f(w,u)2.
A set P (P contains the label of the points) is called best set if and only if there are at least one best pair in P. Two numbers u and v (u,v∈P,u≠v) are called best pair, if for every w∈P, f(u,v)≥g(u,v,w), where f(u,v)=(xu−xv)2+(yu−yv)2−−−−−−−−−−−−−−−−−−√ and g(u,v,w)=f(u,v)+f(v,w)+f(w,u)2.
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1≤n≤1000) -- then number of points.
Each of the following n lines contains two integers xi and yi (−109≤xi,yi≤109) -- coordinates of the i-th point.
The first line contains an integer n (1≤n≤1000) -- then number of points.
Each of the following n lines contains two integers xi and yi (−109≤xi,yi≤109) -- coordinates of the i-th point.
Output
For each test case, output an integer denoting the answer.
Sample Input
331 11 11 130 00 11 010 0
Sample Output
430
/*hdu 5738 Eurekaproblem:求有多少个队列,满足 f(u,v) >= g(u,v,m)solve:f(u,v) >= g(u,v,m) ----> f(u,v) >= f(u,w) + f(w,v); f()即求两点间的距离所以就成了找出有多少点共线. 然后计算对best sets贡献即可.hhh-2016-08-26 19:08:41*/#pragma comment(linker,"/STACK:124000000,124000000")#include <algorithm>#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>#include <vector>#include <math.h>#include <queue>#include <map>#define lson i<<1#define rson i<<1|1#define ll long long#define clr(a,b) memset(a,b,sizeof(a))#define scanfi(a) scanf("%d",&a)#define scanfl(a) scanf("%I64d",&a)#define key_val ch[ch[root][1]][0]#define inf 0x3f3f3f3fusing namespace std;const ll mod = 1e9+7;const int maxn = 1004;ll gcd(ll a,ll b){ if(!a) return b; if(!b) return a; while(a % b != 0) { ll t = a% b; a = b; b = t; } return b;}struct node{ ll x,y;} pnode[maxn];bool cmp(node a,node b){ if(a.x != b.x) return a.x < b.x; return a.y < b.y;}map<pair<ll,ll>,int> mp;ll pow_mod(ll a,ll n){ ll cnt = 1; if(n < 0) return 0; while(n) { if(n & 1) cnt = cnt*a%mod; a = a*a%mod; n >>= 1; } return cnt;}int main(){// freopen("in.txt","r",stdin); int T,n; ll v,u; scanfi(T); while(T--) { scanfi(n); for(int i = 0; i < n; i++) { scanfl(u),scanfl(v); pnode[i].x = u,pnode[i].y = v; } ll ans = 0; sort(pnode,pnode+n,cmp); for(int i =0; i < n; i++) { ll cnt = 0; mp.clear(); for(int j = i+1; j < n; j++) { if(pnode[i].x == pnode[j].x && pnode[i].y == pnode[j].y) cnt++; else { ll tx = pnode[i].x - pnode[j].x; ll ty = pnode[i].y - pnode[j].y; ll t = gcd(tx,ty); if(t) mp[make_pair(tx/t,ty/t)]++; else mp[make_pair(tx,ty)]++; } } if(cnt ) { ans = (ans+pow_mod(2,cnt)-1)%mod; } for(map<pair<ll,ll>,int>::iterator it = mp.begin();it != mp.end();it++) { ll num = (ll)(it->second); ans = (ans+pow_mod(2,cnt)*(pow_mod(2,num)-1)%mod)%mod; } } printf("%I64d\n",ans); } return 0;}
hdu 5738 Eureka
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。