2020-2021:teams:legal_string:组队训练比赛记录:contest8
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest8 [2021/07/30 10:29] 王智彪 |
2020-2021:teams:legal_string:组队训练比赛记录:contest8 [2021/07/31 23:50] (当前版本) lgwza [补题情况] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| ^ 题目 ^ 蒋贤蒙 ^ 王赵安 ^ 王智彪 ^ | ^ 题目 ^ 蒋贤蒙 ^ 王赵安 ^ 王智彪 ^ | ||
| - | | D | 2 | 0 | 0 | | + | | D | 2 | 0 | 1 | |
| - | | E | 0 | 0 | 2 | | + | | E | 0 | 1 | 2 | |
| - | | L | 0 | 0 | 2 | | + | | L | 0 | 1 | 2 | |
| ====== 题解 ====== | ====== 题解 ====== | ||
| 行 116: | 行 116: | ||
| for(int i=0; i<k; i++) { | for(int i=0; i<k; i++) { | ||
| scanf("%lld %lld",&PO.p[i].x,&PO.p[i].y); | scanf("%lld %lld",&PO.p[i].x,&PO.p[i].y); | ||
| - | PO.p[i].id=i+1; | + | PO.p[i].id=i+1;//这里标记一下哪些是小凸包的点 |
| PO1.p[i]=PO.p[i]; | PO1.p[i]=PO.p[i]; | ||
| } | } | ||
| 行 128: | 行 128: | ||
| } | } | ||
| PO1.Graham(po1); | PO1.Graham(po1); | ||
| - | ll ans=po.getarea(); | + | ll ans=po.getarea();//先求一下小凸包面积 |
| ll tans=0; | ll tans=0; | ||
| int l=-1,r=-1; | int l=-1,r=-1; | ||
| 行 139: | 行 139: | ||
| break; | break; | ||
| } | } | ||
| - | if(pp==-100) { | + | if(pp==-100) {//这里要特判没有外面点的情况，也就是大小凸包重合，没有算下去的必要。 |
| printf("%lld.%d\n",ans>>1,ans%2==0?0:5); | printf("%lld.%d\n",ans>>1,ans%2==0?0:5); | ||
| return 0; | return 0; | ||
| } | } | ||
| - | for (int i=0; i<po.n;i++) { | + | for (int i=0; i<po.n;i++) {//暴力求第一个的l,r指针 |
| if ((l==-1)||(((po.p[i]-po1.p[pp])^(po.p[l]-po1.p[pp]))<=0)) { | if ((l==-1)||(((po.p[i]-po1.p[pp])^(po.p[l]-po1.p[pp]))<=0)) { | ||
| l=i; | l=i; | ||
| 行 153: | 行 153: | ||
| ll ts=0; | ll ts=0; | ||
| for(int i=l;i!=r;i=(i+1)%po.n) { | for(int i=l;i!=r;i=(i+1)%po.n) { | ||
| - | ts+=((po.p[i])^(po.p[(i+1)%po.n])); | + | ts+=((po.p[i])^(po.p[(i+1)%po.n]));//暴力算一下多边形面积 |
| } | } | ||
| - | ts+=(po.p[r]^po.p[l]); | + | ts+=(po.p[r]^po.p[l]);//三角剖分算回来 |
| - | tans=max(tans,labs((po1.p[pp]^po.p[l])+(po.p[r]^po1.p[pp])+(po.p[l]^po.p[r]))-labs(ts)); | + | tans=max(tans,labs((po1.p[pp]^po.p[l])+(po.p[r]^po1.p[pp])+(po.p[l]^po.p[r]))-labs(ts));//先求这个点的最大值 三角形面积-多边形面积 |
| for(int i=pp+1;i<po1.n;i++) { | for(int i=pp+1;i<po1.n;i++) { | ||
| while((!(po.p[r]==po1.p[i]))&&((po.p[(r+1)%po.n]-po1.p[i])^(po.p[r]-po1.p[i]))>=0) { | while((!(po.p[r]==po1.p[i]))&&((po.p[(r+1)%po.n]-po1.p[i])^(po.p[r]-po1.p[i]))>=0) { | ||
| - | ts-=(po.p[r]^po.p[l]); | + | ts-=(po.p[r]^po.p[l]);//都是三角剖分 |
| ts+=(po.p[r]^po.p[(r+1)%po.n]); | ts+=(po.p[r]^po.p[(r+1)%po.n]); | ||
| ts+=(po.p[(r+1)%po.n]^po.p[l]); | ts+=(po.p[(r+1)%po.n]^po.p[l]); | ||
| 行 165: | 行 165: | ||
| } | } | ||
| while((!(po.p[l]==po1.p[i]))&&((po.p[(l+1)%po.n]-po1.p[i])^(po.p[l]-po1.p[i])) <= 0) { | while((!(po.p[l]==po1.p[i]))&&((po.p[(l+1)%po.n]-po1.p[i])^(po.p[l]-po1.p[i])) <= 0) { | ||
| - | ts-=(po.p[r]^po.p[l]); | + | ts-=(po.p[r]^po.p[l]);//都是三角剖分 |
| ts-=(po.p[l]^po.p[(l+1)%po.n]); | ts-=(po.p[l]^po.p[(l+1)%po.n]); | ||
| l=(l+1)%po.n; | l=(l+1)%po.n; | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest8.1627612189.txt.gz · 最后更改: 2021/07/30 10:29 由 王智彪
