2020-2021:teams:die_java:front_page_springtraining6
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:die_java:front_page_springtraining6 [2020/05/23 13:02] fyhssgss [[2019 ICPC Asia Taipei-Hsinchu Regional]] |
2020-2021:teams:die_java:front_page_springtraining6 [2020/07/10 14:42] (当前版本) fyhssgss |
||
|---|---|---|---|
| 行 485: | 行 485: | ||
| 补题by fyh | 补题by fyh | ||
| - | 去除重复点，求出凸包,然后旋转卡壳枚举每个点的最远点，然后暴力计算四边形面积 | + | 求凸包后先枚举对角线，然后通过旋转卡壳把剩下两个点找到，复杂度$O(n^2)$ |
| - | 退化情况有： | + | 当求出凸包只有三个点的时候，所得四边形是一个凹四边形。 |
| - | + | ||
| - | 凸包上只有三个点，那么这个四边形一定是一个凹四边形，计算出最小三角形面积然后用凸包面积减去小三角形面积就可以。 | + | |
| - | + | ||
| - | 凸包上只有两个点：（再%%**%%的见） | + | |
| + | <hidden 代码> | ||
| + | <code cpp> | ||
| + | #include<iostream> | ||
| + | #include<algorithm> | ||
| + | #include<cmath> | ||
| + | #include<cstdio> | ||
| + | #include<cstring> | ||
| + | #include<cstdlib> | ||
| + | #include<queue> | ||
| + | using namespace std; | ||
| + | #define mem(a,b) memset(a,b,sizeof(a)) | ||
| + | typedef long long LL; | ||
| + | typedef pair<int,int> PII; | ||
| + | #define X first | ||
| + | #define Y second | ||
| + | inline int read() | ||
| + | { | ||
| + | int x=0,f=1;char c=getchar(); | ||
| + | while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} | ||
| + | while(isdigit(c)){x=x*10+c-'0';c=getchar();} | ||
| + | return x*f; | ||
| + | } | ||
| + | const int maxn=2010; | ||
| + | const double eps=1e-8; | ||
| + | struct Point{ | ||
| + | double x,y; | ||
| + | Point() {} | ||
| + | Point(double _1,double _2):x(_1),y(_2) {} | ||
| + | Point operator - (const Point&s) const {return Point(x-s.x,y-s.y);} | ||
| + | double operator * (const Point&s) const {return x*s.y-y*s.x;} | ||
| + | double len() {return x*x+y*y;} | ||
| + | }a[maxn],p[maxn]; | ||
| + | typedef Point Vec; | ||
| + | double dis(Point a,Point b){ | ||
| + | return (a-b).len(); | ||
| + | } | ||
| + | double S(Point a,Point b,Point c){ | ||
| + | return abs((b-a)*(c-a)); | ||
| + | } | ||
| + | bool judgeOnLeft(int p0,int p1,int p2){ | ||
| + | double s=(a[p1]-a[p0])*(a[p2]-a[p0]); | ||
| + | return s<0 || (s==0 && dis(a[p1],a[p0])>=dis(a[p2],a[p0])); | ||
| + | } | ||
| + | bool cmp(Point p0,Point p1){ | ||
| + | double s=(p0-a[1])*(p1-a[1]); | ||
| + | return s<0 || (s==0 && dis(p0,a[1])>=dis(p1,a[1])); | ||
| + | } | ||
| + | int n,top,sta[maxn]; | ||
| + | double ans; | ||
| + | int Graham() | ||
| + | { | ||
| + | int temp=1,m=0; | ||
| + | for(int i=2;i<=n;i++) | ||
| + | if(a[i].x<a[temp].x || (a[i].x==a[temp].x && a[i].y<a[temp].y))temp=i; | ||
| + | swap(a[temp],a[1]); | ||
| + | sort(a+2,a+n+1,cmp); | ||
| + | a[n+1]=a[1]; | ||
| + | sta[++top]=1;sta[++top]=2; | ||
| + | for(int i=3;i<=n+1;i++) | ||
| + | { | ||
| + | while(top>1 && judgeOnLeft(sta[top-1],i,sta[top]))top--; | ||
| + | sta[++top]=i; | ||
| + | } | ||
| + | for(int i=1;i<=top;i++)p[m++]=a[sta[i]];//,printf("%lf %lf\n",p[i-1].x,p[i-1].y); | ||
| + | return m-1; | ||
| + | } | ||
| + | double solve() | ||
| + | { | ||
| + | if(n<4)return 0.000; | ||
| + | double ans=0; | ||
| + | for(int i=0;i<n;i++) | ||
| + | { | ||
| + | int k=i+1,l=i+3; | ||
| + | for(int j=i+2;j<n;j++) | ||
| + | { | ||
| + | while(S(p[i],p[j],p[(k+1)%n])-S(p[i],p[j],p[k])>-eps)k=(k+1)%n; | ||
| + | while(S(p[i],p[j],p[(l+1)%n])-S(p[i],p[j],p[l])>-eps)l=(l+1)%n; | ||
| + | ans=max(ans,S(p[i],p[j],p[k])+S(p[i],p[j],p[l])); | ||
| + | // printf("%d %d %d %d\n",i,j,k,l); | ||
| + | } | ||
| + | } | ||
| + | return ans/2.0; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | n=read(); | ||
| + | if(n<3)return puts("0.000"),0; | ||
| + | for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y); | ||
| + | n=Graham(); | ||
| + | printf("%.3lf\n",solve()); | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| ===== 训练实况 ===== | ===== 训练实况 ===== | ||
2020-2021/teams/die_java/front_page_springtraining6.1590210140.txt.gz · 最后更改: 2020/05/23 13:02 由 fyhssgss
