题意：
给定平面上任意三点不共线的一个点集，每次询问三个点，求三个点组成的三角形中内包含点集中多少个点。
点数1000，询问100000，没有三点共线
题解:
(引用了某神牛的图。。)
分成7个区域，然后0=(0+2)+(0+6)+(0+4)+(1+2+3)+(3+4+5)+(1+5+6)-2*(1+2+3+4+5+6)
然后通过种种极角排序完的单调性n^2logn预处理，O（1）回答询问。
抑郁了，调了一晚上，好不容易找了错了（角标打错了。。。），对拍了半天都没发现错（没有三点共线时是对的，有三点共线就错的离谱了。。但是，题目说了没有了。。）
哪位神犇如果发现我哪里写错了请告诉我一声，感谢！
View Code
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <cmath> 7 8 #define N 1010 9 #define EPS 1e-7 10 #define BUG system("pause") 11 #define CA puts("ca") 12 13 using namespace std; 14 15 struct PO 16 { 17 double x,y; 18 int bh; 19 double angle; 20 }p[N],px[N],o; 21 22 double ag[N][N]; 23 int lt[N][N],g[N][N]; 24 int n,m; 25 26 inline void prt(PO &a) 27 { 28 printf("Po:%d %lf %lf %lf\n",a.bh,a.x,a.y,a.angle); 29 } 30 31 inline void read() 32 { 33 scanf("%d",&n); 34 for(int i=1;i<=n;i++) 35 { 36 scanf("%lf%lf",&p[i].x,&p[i].y); 37 p[i].bh=i; 38 } 39 } 40 41 inline PO operator -(PO a,PO b) 42 { 43 PO c; 44 c.x=a.x-b.x; c.y=a.y-b.y; 45 return c; 46 } 47 48 inline PO operator +(PO a,PO b) 49 { 50 PO c; 51 c.x=a.x+b.x; c.y=a.y+b.y; 52 return c; 53 } 54 55 inline int dc(double x) 56 { 57 if(x>EPS) return 1; 58 else if(x<-EPS) return -1; 59 return 0; 60 } 61 62 inline double cross(PO &a,PO &b,PO &c) 63 { 64 return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); 65 } 66 67 inline bool cmpn(const PO &a,const PO &b)//逆时针 68 { 69 return a.angle<b.angle; 70 } 71 72 inline bool cmps(const PO &a,const PO &b)//顺时针 73 { 74 return a.angle>b.angle; 75 } 76 77 inline void prep() 78 { 79 for(int i=1;i<=n;i++) 80 { 81 for(int j=1;j<=n;j++) 82 if(i!=j) px[j]=p[j]-p[i],px[j].bh=j; 83 swap(px[n],px[i]); 84 for(int j=1;j<n;j++) px[j].angle=atan2(px[j].y,px[j].x); 85 sort(px+1,px+n,cmpn); 86 //for(int j=1;j<n;j++) prt(px[j]);CA; 87 for(int j=1;j<n;j++) ag[i][j]=px[j].angle;//逆时针保存所有点相对于i的极角 88 int ct=0; 89 for(int t1=1,t2=2;t1<n;t1++,ct--) 90 { 91 if(t1==t2) t2=(t2%(n-1))+1,ct++; 92 while(dc(cross(o,px[t1],px[t2]))>0) t2=(t2%(n-1))+1,ct++; 93 lt[i][px[t1].bh]=ct;//向量的左侧的点数 94 //printf("%d %d %d\n",t1,t2,ct); 95 } 96 } 97 /*for(int i=1;i<=n;i++) 98 for(int j=1;j<=n;j++) 99 printf("%d %d %d\n",i,j,lt[i][j]); 100 */ 101 } 102 103 inline int getpos(PO mo,PO a) 104 { 105 double gg=atan2(a.y-mo.y,a.x-mo.x); 106 //cout<<"---- "<<gg<<" "<<mo.bh<<endl; 107 int l=1,r=n-1,mid,res; 108 while(l<=r) 109 { 110 mid=(l+r)>>1; 111 if(dc(ag[mo.bh][mid]-gg)<=0) l=mid+1,res=mid; 112 else r=mid-1; 113 } 114 return res; 115 } 116 117 inline int getnum(PO &a,PO &b,PO &c)//得到ab到ac中间夹得点数 118 { 119 int t1=g[a.bh][b.bh]; 120 int t2=g[a.bh][c.bh]; 121 //printf("%d %d\n",t1,t2); 122 if(t2>t1) return t2-t1-1; 123 else return n-3-(t1-t2-1); 124 } 125 126 inline void prev() 127 { 128 for(int i=1;i<=n;i++) 129 for(int j=1;j<=n;j++) 130 if(i!=j) g[i][j]=getpos(p[i],p[j]); 131 } 132 133 inline void inorder(int *a,PO *tmp)//按顺时针排序 134 { 135 for(int i=1;i<=3;i++) {tmp[i]=p[a[i]];tmp[i].bh=a[i];} 136 PO c=(tmp[1]+tmp[2]+tmp[3]); 137 c.x/=3; c.y/=3; 138 for(int i=1;i<=3;i++) tmp[i].angle=atan2(tmp[i].y-c.y,tmp[i].x-c.x); 139 sort(tmp+1,tmp+1+3,cmps); 140 //for(int i=1;i<=3;i++) prt(tmp[i]);// 141 } 142 143 inline void go() 144 { 145 prep(); 146 prev(); 147 //for(int i=1;i<=n;i++){ 148 // for(int j=1;j<n;j++) printf("%lf ",ag[i][j]);printf("\n");}//BUG; 149 scanf("%d",&m); 150 int a[7];PO sk[7]; 151 for(int i=1,sa,sb,sc,sd;i<=m;i++) 152 { 153 scanf("%d%d%d",&a[1],&a[2],&a[3]); 154 a[1]++; a[2]++; a[3]++; 155 inorder(a,sk); 156 sa=getnum(sk[1],sk[3],sk[2]); 157 sb=getnum(sk[2],sk[1],sk[3]); 158 sc=getnum(sk[3],sk[2],sk[1]); 159 sd=lt[sk[1].bh][sk[2].bh]+lt[sk[2].bh][sk[3].bh]+lt[sk[3].bh][sk[1].bh]; 160 //printf("%d %d %d %d\n",sa,sb,sc,sd); 161 printf("%d\n",-2*(n-3)+sa+sb+sc+sd); 162 } 163 } 164 165 int main() 166 { 167 //freopen("t.txt","r",stdin); freopen("1.txt","w",stdout); 168 int cas; scanf("%d",&cas); 169 for(int i=1;i<=cas;i++) 170 { 171 printf("Case %d:\n",i); 172 read(),go(); 173 } 174 return 0; 175 }