https://nanti.jisuanke.com/t/15429
题目大意：给出平面内$n$个整数坐标点，保证无三点共线。可以进行若干次连线，每次选择一个点对连接线段，但是任意两条线段都不得在给定的$n$个点之外有交点。问连线完成后，最多能构造出多少个三角形。
解题关键：
小于三个点的情况答案为零。考虑三个点的情况，由于三点不共线，必然构成一个三角形。现加入第四个点，若其在原三角形外部，则称其为外点，可以新构造$1$个三角形；若其在原三角形内部，则称其为内点，可以新构造$3$个三角形。故要尽可能让更多的点成为内点。假设这$n$个点的凸包上有$m$个点，这$m$个点必然只能是外点，将凸包剖分成$m - 2$个三角形后，剩余$n - m$个点均为内点，答案即为$3n - 2m - 2$。
其次，凸包模板。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 struct point{ 5 ll x,y; 6 }s[1002],p[1002]; 7 int n,top; 8 double dis(point a,point b){ 9 return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y)); 10 } 11 double cross(point a,point b,point c,point d){ 12 return (b.x-a.x)*(d.y-c.y)-(b.y-a.y)*(d.x-c.x); 13 } 14 bool cmp(point a,point b){ 15 double z=cross(p[0],a,p[0],b); 16 return z?z>0:dis(p[0],a)<dis(p[0],b);//这里不确定 17 } 18 void findpoint(){ 19 for(int i=1;i<n;i++){ 20 if(p[i].y<p[0].y||(p[i].y==p[0].y&&p[i].x<p[0].x)) swap(p[i],p[0]); 21 } 22 } 23 void scanner(){ 24 findpoint(); 25 sort(p+1,p+n,cmp); 26 s[0]=p[0],s[1]=p[1],top=2; 27 for(int i=2;i<n;i++){ 28 while(cross(s[top-2],s[top-1],s[top-1],p[i])<0) top--; 29 s[top++]=p[i]; 30 } 31 } 32 int main(){ 33 int t; 34 cin>>t; 35 while(t--){ 36 memset(p,0,sizeof p); 37 memset(s,0,sizeof s); 38 cin>>n; 39 for(int i=0;i<n;i++){ 40 cin>>p[i].x>>p[i].y; 41 } 42 scanner(); 43 if(n<3){printf("0\n");continue;} 44 printf("%lld\n",1ll*3*n-2*top-2); 45 } 46 }
原文：http://www.cnblogs.com/elpsycongroo/p/6858808.html