首页 > 代码库 > [凸包]Triangles
[凸包]Triangles
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 }
[凸包]Triangles
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。