选点问题

Description

陶陶和鹏鹏在玩一个十分有趣的游戏!已知平面上有n个不同的点(保证不存在任意3个点共线)，陶陶首先任意选取其中2个不同的点a，b，并连线得到线段AB，之后鹏鹏从剩下的n-2个点中任意选取2个不同的点c，d，并同样连线得到线段CD。对于陶陶选择的点a，b，鹏鹏可能有若干种选择c，d的方案，使得CD与AB相交!易知，陶陶有n(n—1)／2种方案选择a，b。对于陶陶的第i种选择，假设鹏鹏有Ki种方案选择c，d使得AB和CD相交。 ★编程任务：请计算输出陶陶和鹏鹏游戏的估价值T，其定义为：其中Fib(x)表示第x项斐波那契数，它满足：

由于T能比较大，请输出T模上1000000007的结果。

Input Format

输入文件名为point．in。第一行一个整数n，表示平面上有n(n<=200)个点。接下来n行，给出n个点的坐标(xi，yi)。输入的坐标均为整数，取值范围是：-100，000到100，000。

Output Format

输出文件名为point．out。输出一行一个整数，表示T模上1，000，000，007的结果。

Sample Input

Sample Output

4

菲波那切数列可以暴力求，然后这个公式也没有什么能变形的地方，反正就是告诉你：求相交线段的数目。
我们考虑每个点所作出的贡献。

如图，对于每个O，我们枚举A点和B点，此时，我们只需要计算OA,OB的反向延长线范围内的点数num,然后tot[A][B]-=num即可！，至于为什么呢，因为我们计算这部分点和O相连的时候，无法和AB相交，然而我们却无法直接计算，因为OAB三角形内还有部分不合法的点对，因此我们利用容斥原理，每次只减去一个方向的点，最后得到的便是答案。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<string>
 6 #include<algorithm>
 7 #define ll long long
 8 const ll MOD=1000000007;
 9 const double pi=acos(-1),eps=1e-13;
10 int f[200005],tot[205][205];
11 int n;
12 struct Point{
13     int x,y,id;
14     double ang;
15 }p[200005],t[200005];
16 int sign(double x){
17     return x<-eps?-1:x>eps;
18 }
19 ll powit(ll x,int y){
20     ll ans=1;
21     while (y){
22         if (y&1) ans=(ans*x)%MOD;
23         x=(x*x)%MOD;
24         y/=2; 
25     }
26     return ans;
27 }
28 bool cmp(Point x,Point y){
29     return x.ang<y.ang;
30 }
31 void Fib(){
32     f[0]=1;
33     f[1]=1;
34     for (int i=2;i<=n*n;i++) f[i]=(f[i-1]+f[i-2])%(MOD-1);
35 }
36 void solve(){
37     for (int i=1;i<=n;i++){
38         int cnt=0;
39         for (int j=1;j<=n;j++){
40             if (j==i) continue;
41             p[++cnt]=t[j];
42             p[cnt].ang=std::atan2(t[j].y-t[i].y,t[j].x-t[i].x);
43         }
44         std::sort(p+1,p+n,cmp);
45         for (int j=1;j<n;j++){
46             p[n-1+n-1+j]=p[n-1+j]=p[j];
47             p[n-1+j].ang=p[j].ang+2*pi;
48             p[n-1+n-1+j].ang=p[n-1+j].ang+2*pi;
49         }
50         int l=1;
51         for (int j=1;j<n;j++){
52             int r=j+1;
53             while (sign(p[l].ang-p[j].ang-pi)<0) ++l;
54             for (int k=j+1;sign(p[k].ang-p[j].ang-pi)<=0;k++){
55                  while (sign(p[r+1].ang-p[k].ang-pi)<=0) r++;
56                  tot[p[k].id][p[j].id]=tot[p[j].id][p[k].id]+=k-j-1-(r-l+1); 
57             }  
58         }
59     }
60     ll     ans=1;
61     for (int i=1;i<=n;i++)
62      for (int j=i+1;j<=n;j++){
63          tot[i][j]/=2;
64          ans=(ans*(1+powit(tot[i][j],f[tot[i][j]])%MOD))%MOD;
65      }
66     printf("%lld",ans); 
67 }
68 int main(){
69     scanf("%d",&n);
70     for (int i=1;i<=n;i++){
71         scanf("%d%d",&t[i].x,&t[i].y);
72         t[i].id=i;
73     }
74     Fib();
75     solve();
76 }