2016 Multi-University Training Contest 2 1005 hdu 5738計算ジオメトリ

リンク:ここをスタンプ
Eureka
Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
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.
 
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.
 
Output
For each test case, output an integer denoting the answer.
 
Sample Input
3
3
1 1
1 1
1 1
3
0 0
0 1
1 0
1
0 0
 
Sample Output
4
3
0
 
考え方:
まず重くして、テーマの要求の集合は1本の線分です.そしてu,vは線分の2つの端点である.では、ポイントセットの各セグメントについて、各セグメントの寄与を統計します.
線分にk個の点があるとすると、寄与は(C(k,2)+C(k,3)+…+C(k,k))=2^k−1−kとなる.しかし、複数の線分の交点にg個のポイントがちょうど存在する場合
では、多算を減算する必要があります.このポイントをm本の線分にぴったりと設定すると、(m-1)回多く計算されます.マルチコンピューティングの寄与は(m-1)*((2^g)-g-1)である.
問題は、1つのセグメントにどれだけの点があるか、1つの点がどれだけのセグメントに現れるかということです.ダイレクトn*nlogn処理
カードの精度に注意して、long doubleをつけましょう
コード:

#include
#include
#include
#include
#include
#include
#include 
#include
#include
#include