2020-2021:teams:die_java:front_page_springtraining6
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:front_page_springtraining6 [2020/05/23 00:43] fyhssgss |
2020-2021:teams:die_java:front_page_springtraining6 [2020/07/10 14:42] (当前版本) fyhssgss |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== [2019 Multi-University Training Contest 1] ====== | + | ====== 2019 ICPC Asia Taipei-Hsinchu Regional ====== |
| - | [[|比赛网址]] | + | [[http://codeforces.com/gym/102460|比赛网址]] |
| ===== 训练详情 ===== | ===== 训练详情 ===== | ||
| * 时间:2020-5-17 13:00~18:00 | * 时间:2020-5-17 13:00~18:00 | ||
| - | * rank: | + | * rank:''%%93/506%%'' |
| - | * 完成情况： | + | * 完成情况：''%%7/10/13%%'' |
| ===== 题解 ===== | ===== 题解 ===== | ||
| 行 24: | 行 24: | ||
| <code cpp> | <code cpp> | ||
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| - | #include<map> | ||
| using namespace std; | using namespace std; | ||
| #define mem(a,b) memset(a,b,sizeof(a)) | #define mem(a,b) memset(a,b,sizeof(a)) | ||
| 行 467: | 行 466: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | \\ | ||
| ===== K Automatic Control Machine ===== | ===== K Automatic Control Machine ===== | ||
| 行 486: | 行 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> | ||
| + | ===== 训练实况 ===== | ||
| - | 凸包上只有两个点：（再%%**%%的见） | + | 0~15min hxm，wxg横扫**K,C,D**三个签到题 |
| - | ===== 训练实况 ===== | + | 15min~1h20min 口糊出**A**,fyh开写**A**,wxg,hxm讨论**E**,并讨论出来 |
| + | |||
| + | 1h20min~1h28min **A** 本机编译错误，哈希出现问题 hxm开**E**,并A | ||
| + | |||
| + | 1h28min~1h??min 想出**H**,写**H** 并A | ||
| + | |||
| + | 2h~2h14min hxmA**J**,其他人在读题 | ||
| + | 2h14min~2h36min fyhA**A**, | ||
| + | 2h36min~ 读完所有题并确认全不可做，结束比赛 | ||
| ===== 训练总结 ===== | ===== 训练总结 ===== | ||
| + | 像**A**这种代码量较大的题要尽量往后放，否则会增加罚时 | ||
| + | 尽早放弃 | ||
2020-2021/teams/die_java/front_page_springtraining6.1590165838.txt.gz · 最后更改: 2020/05/23 00:43 由 fyhssgss
