HDU5784(计算几何）

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 using namespace std;
 6 #define eps 1e-8
 7 
 8 struct P{
 9     long long x,y;
10     int f;
11     friend P operator -(P a,P b){
12         return (P){a.x-b.x,a.y-b.y};
13     }
14 }a[20008],b[20008],S;
15 
16 int n,m;
17 
18 inline long long cross(P a,P b,P c){  //ab X ac
19     return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
20 }
21 
22 inline int calc(P a){
23     if (a.x>0 && a.y==0) return 1;
24     if (a.x>0 && a.y>0) return 1;
25     if (a.x==0 && a.y>0) return 2;
26     if (a.x<0 && a.y>0) return 2;
27     if (a.x<0 && a.y==0) return 3;
28     if (a.x<0 && a.y<0) return 3;
29     if (a.x==0 && a.y<0) return 4;
30     if (a.x>0 && a.y<0) return 4;
31 }
32 
33 inline bool cmp(const P a,const P b) {
34     if (a.freturn true;
35     if (a.f>b.f) return false;
36     long long tmp=cross(S,a,b);
37     if (tmp>0) return true;
38     return false; 
39 }
40 
41 inline bool ok(P a,P b,P c){
42     long long tmp=(b.x-a.x)*(c.x-a.x)+(b.y-a.y)*(c.y-a.y);
43     if (tmp>0) return true;
44     return false;
45 }
46 
47 int main(){
48     while (~scanf("%d",&n)){
49         for (int i=1;i<=n;i++) scanf("%I64d %I64d",&a[i].x,&a[i].y);
50         long long sum=0;
51         for (int ii=1;ii<=n;ii++){
52             S=a[ii]; m=0; 
53             for (int j=1;j<=n;j++)
54                 if (j!=ii) b[++m]=a[j];
55             for (int i=1;i<=m;i++) b[i].f=calc(b[i]-S);
56             sort(b+1,b+m+1,cmp);
57             int i=1,j=1,k=1;
58             while (ok(S,b[i],b[j]) && cross(S,b[i],b[j])>=0 && j<=m) j++;
59             if (j==m+1) continue;
60             j--; k=j+1;
61             while (i<=m)
62             {
63                 if (!ok(S,b[i],b[k])){        
64                     while (!ok(S,b[i],b[k+1]) && k;
65                     sum+=k-j;
66                 }
67                 i++;
68                 if (ji; 
69                 while (ok(S,b[i],b[j+1]) && cross(S,b[i],b[j+1])>0 && j;
70                 if (k<=j) k=j+1;
71                 if (k>m) break;
72             }        
73         }
74         long long p=1ll*n*(n-1)*(n-2)/6;
75         printf("%I64d\n",p-sum);
76     }
77 }