ICPC2021上海热身Two Point Removal

Created on November 27, 2021

2021   ·   computational geometry

今天ICPC上海热身赛,本来我是负责计算几何的

但我队伍做题把A分为两种情况

1.删去两个相邻的点使得线段最短

2.删去两个不相邻的点使得线段最短

第二种如何找出不相邻的两个点的时候，把n*n优化想不出，后面学长来写了，但写的时候我提起昨天CF的B题（模拟）结构体排序，保存排序前的下标，有了这一思路，只需要取排序后的四个，判断4个判断是不是相邻和可以使线段减少最多即可

最终顺利签了到

这是赛后我的个人代码

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #define x first 
 5 #define y second
 6 using namespace std;
 7 typedef pair<double,double> PDD;
 8 
 9 PDD operator - (const PDD& A,const PDD& B)
10 {
11     return PDD(A.x-B.x,A.y-B.y);
12 }
13 double get_dist(PDD A)
14 {
15     return sqrt(A.x*A.x+A.y*A.y);
16 }
17 struct node
18 {
19     double ss;
20     int shenfen;
21 }b[100010];
22 
23 bool cmp1(node c,node d)
24 {
25     return c.ss>d.ss;
26 }
27 
28 PDD a[100010];
29 int main()
30 {
31     int n;
32     cin>>n;
33     for(int i=1;i<=n;i++)
34     {
35         double sy;
36         cin>>sy;
37         a[i]={double(i),sy};
38     }
39     a[0]={0.0,0.0},a[n+1]={(double)n+1.0,0.0};
40     
41     double s1=0,s2=0;
42     for(int i=1;i<=n+1;i++)
43     {
44         s1+=get_dist(a[i]-a[i-1]);
45     }
46     s2=s1;
47     for(int i=1;i<=n;i++)
48     {
49         b[i].ss=get_dist(a[i]-a[i-1])+get_dist(a[i+1]-a[i])-get_dist(a[i+1]-a[i-1]);
50         b[i].shenfen=i;
51     }
52     sort(b+1,b+1+n,cmp1);
53     
54     double max1=0.0;
55     for(int i=1;n>=3&&i<=4&&i<=n;i++)
56     {
57         if(b[i].ss+b[i+1].ss>max1&&abs(b[i].shenfen-b[i+1].shenfen)>1)
58         {
59             max1=b[i].ss+b[i+1].ss;
60         }
61     }
62     s1-=max1;
63 
64     
65     double max_two=-1e4;
66     for(int i=1;i<=n-1;i++)
67     {
68         if(get_dist(a[i]-a[i-1])+get_dist(a[i+1]-a[i])+get_dist(a[i+2]-a[i+1])-get_dist(a[i+2]-a[i-1])>=max_two)
69         {
70             max_two=get_dist(a[i]-a[i-1]) + get_dist(a[i+1]-a[i]) + get_dist(a[i+2]-a[i+1])-get_dist(a[i+2]-a[i-1]);
71             
72         }
73     }
74     s2-=max_two;
75 
76     if(s1-s2>1e-8)
77     {
78         printf("%.8lf\n",s2);
79     }
80     else
81     {
82         printf("%.8lf\n",s1);
83     }
84     
85     return 0;
86     
87 }