[计算几何+图论]doge

题意

在平面直角坐标系上,你有一只doge在原点处。doge被绳子拴住了,绳子不会打结,没有弹性(但很柔软),并且长度为L。平面上有一些目标,因此你的doge会按照顺序去捡起它们,但是doge只能走直线。此外平面上还有一些障碍,视为一些点,狗在绕圈时可能会把绳子缠在上面。问L的最小值。

坐标均为整数,所有数的绝对值都不超过1000。物品和障碍物数量和不超过100。

“缠绕”:

[计算几何+图论]doge

 

[计算几何+图论]doge

注意,虽然画的物品和障碍物是一个圈,但实际上可看做一个点。


 

思考

一些性质:

1.乱套模板是不可做的。

2.答案为doge依次捡起1~i物品中,绳子能缩短的最大值。因为doge可以沿这个能缩短的路径走,捡起一个物品后能回溯到原点。

3.doge在以此捡起1~i的物品中,doge一定会走最短路。因为这才更有可能使答案更优。

4.最短的路径是不能乱走的,但仿佛与两点与线段的位置有关。

 

先将所有点旋转一个角度,使得他们都不在同一条与x轴垂直的线上。

[计算几何+图论]doge

红线是doge可能走的路径。而这个答案为所有红线绷紧后的长度。

而此时对于有经过顺序的红线,它是否弯折,怎么弯折,只跟它现在经过某个障碍物上下面的顺序有关(图中的上下是黑色圈的上部分线段和下部分线段)。对于一个经过上下顺序相同的线段,可看做它们是等价的(虽然长度可能不同)。也就是说,若一种红线经过上下顺序已经给定,它长度的最小值就是(所有(有这种顺序的)(红线的)(长度的))最小值。

这个顺序我们可以表示成一个类似于括号序列的东西。如上图,红线必须经过的顺序为1-2-3-4-4+3+2+1+,代表了它依次经过了哪个障碍,上面还是下面。

先假我们已经会求出一个序列的答案。

 

5.若某次新添加一个物品后,序列最后中出现x+x+或x-x-,可将其直接删去(即倒数第二个和最后一个)。

如图:

[计算几何+图论]doge

由于1+已经在上一次中得到了走到左边的答案,又因为这一次走到了右边,所以不会受到它的影响。

 

6.红线的序列为一些线段的序列拼接而成。并且线段的头尾一定在障碍物或原点或终点处。

直观的想,头尾代表了一个转折点,而转折点缩紧后一定会靠着障碍物。当然也可以三角形不等式说明。

 

有了这些性质,我们就可以根据序列建一张图。其中每条边代表了从一个障碍物(或起点)走到另一个障碍物(或终点)所需的长度,它能在图中当且仅当这条线段以此经过障碍物的上下顺序能匹配相应位置红线的序列。从起到向终点跑最短路,即为答案。

 

说了这么多,其实还是要多想。


 

代码

[计算几何+图论]doge
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const double eps=1E-10;
  4 const double pi=acos(-1);
  5 const double INF=INT_MAX;
  6 const int maxn=1E2+5;
  7 int q,n,m,top;
  8 double ans,f[123456];
  9 bool vis[maxn];
 10 int size,head[123456];
 11 struct pt
 12 {
 13     double x,y;
 14     pt(double a=0,double b=0)
 15     {
 16         x=a,y=b;
 17     }
 18     void operator=(pt A)
 19     {
 20         x=A.x,y=A.y;
 21     }
 22     double operator*(pt A)
 23     {
 24         return x*A.y-y*A.x;
 25     }
 26     pt operator-(pt A)
 27     {
 28         return pt(x-A.x,y-A.y);
 29     }
 30 }target[maxn],barrier[maxn];
 31 struct inf
 32 {
 33     int id,x;
 34     inf(int a=0,int b=0)
 35     {
 36         id=a,x=b;
 37     }
 38 }S[12345];
 39 struct edge
 40 {
 41     int to,next;
 42     double w;
 43 }E[123456];
 44 //////////////////////////////////////////////////////////////////
 45 //polygon
 46 //////////////////////////////////////////////////////////////////
 47 bool cmp(pt A,pt B)
 48 {
 49     return A.x<B.x;
 50 }
 51 pt rotate(pt A,double ra)
 52 {
 53     return pt(A.x*cos(ra)-A.y*sin(ra),A.x*sin(ra)+A.y*cos(ra));
 54 }
 55 int face(pt A,pt B,pt C)
 56 {
 57     double y=(B.y-A.y)/(B.x-A.x)*(C.x-A.x);
 58     if(A.y+y>=C.y)
 59         return 1;
 60     return -1;
 61 }
 62 bool inside(pt A,pt B,pt C)
 63 {
 64     return min(A.x,B.x)<=C.x&&C.x<=max(A.x,B.x);
 65 }
 66 double dis(pt A,pt B)
 67 {
 68     return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
 69 }
 70 int cross(pt A,pt B)
 71 {
 72     double d=A*B;
 73     if(d>eps)
 74         return 1;
 75     else
 76         return -1;
 77 }
 78 void push(inf A)
 79 {
 80     if(A.id==S[top].id&&A.x==S[top].x)
 81         --top;
 82     else
 83         S[++top]=A;
 84 }
 85 //////////////////////////////////////////////////////////////////
 86 //polygon
 87 //////////////////////////////////////////////////////////////////
 88 
 89 
 90 //////////////////////////////////////////////////////////////////
 91 //graph
 92 //////////////////////////////////////////////////////////////////
 93 void add(int u,int v,double w)
 94 {
 95     E[++size].to=v;
 96     E[size].next=head[u];
 97     E[size].w=w;
 98     head[u]=size;
 99 }
100 void clear()
101 {
102     for(int i=0;i<=top+1;++i)
103         head[i]=0;
104     size=0;
105 }
106 double spfa()
107 {
108     for(int i=0;i<=top;++i)
109         f[i]=INF;
110     f[0]=0;
111     vis[0]=1;
112     queue<int>Q;
113     Q.push(0);
114     while(!Q.empty())
115     {
116         int u=Q.front();
117         vis[u]=0;
118         Q.pop();
119         for(int i=head[u];i;i=E[i].next)
120         {
121             int v=E[i].to;
122             double nw=E[i].w+f[u];
123             if(nw<f[v])
124             {
125                 f[v]=nw;
126                 if(!vis[v])
127                 {
128                     vis[v]=1;
129                     Q.push(v);
130                 }
131             }
132         }
133     }
134     return f[top--];
135 }
136 bool check(int l,int r)
137 {
138     for(int i=l+1;i<=r-1;++i)
139         if(face(barrier[S[l].id],barrier[S[r].id],barrier[S[i].id])!=S[i].x)
140             return false;
141     return true;
142 } 
143 double get(int x)
144 {
145     clear();
146     barrier[n+m+1]=target[x];
147     push(inf(n+m+1,0));
148     for(int i=1;i<=top;++i)
149         for(int j=i+1;j<=top;++j)
150             if(check(i,j))
151                 add(i,j,dis(barrier[S[i].id],barrier[S[j].id]));
152     for(int i=1;i<=top;++i)
153         if(check(0,i))
154             add(0,i,dis(pt(0,0),barrier[S[i].id]));
155     return spfa();
156 }
157 
158 //////////////////////////////////////////////////////////////////
159 //graph
160 //////////////////////////////////////////////////////////////////
161 
162 void solve()
163 {
164     top=ans=0;
165     cin>>n>>m;
166     for(int i=1;i<=n;++i)
167     {
168         cin>>target[i].x>>target[i].y;
169         target[i].x+=0.00001;
170         target[i].y+=0.00001;
171         target[i]=rotate(target[i],pi/3);
172     }
173     for(int i=1;i<=m;++i)
174     {
175         cin>>barrier[i].x>>barrier[i].y;
176         barrier[i].x-=0.00001;
177         barrier[i].y-=0.00001;
178         barrier[i]=rotate(barrier[i],pi/3);
179     }
180     sort(barrier+1,barrier+m+1,cmp);
181     pt now(0,0);
182     for(int i=1;i<=n;++i)
183     {
184         if(target[i].x>now.x)
185         {
186             for(int j=1;j<=m;++j)
187                 if(inside(now,target[i],barrier[j]))
188                     push(inf(j,face(now,target[i],barrier[j])));
189         }
190         else
191         {
192             for(int j=m;j>=1;--j)
193                 if(inside(now,target[i],barrier[j]))
194                     push(inf(j,face(now,target[i],barrier[j])));
195         }
196         now=target[i];
197         double g=get(i);
198         ans=max(ans,g);
199     }
200     cout<<fixed<<setprecision(2)<<ans<<endl;
201 }
202 int main()
203 {
204     ios::sync_with_stdio(false);
205     cin>>q;
206     while(q--)
207         solve();
208     return 0;
209 }
210 /*
211 2
212 8  4
213 2  -1
214 3  0
215 3  2
216 0  1
217 3  2
218 3  0
219 2  -1
220 0  0
221 1  0
222 2  0
223 1  1
224 2  1
225 */
226 
227 
228 /*
229 5.00
230 */
View Code

 

上一篇:【洛谷P3645】雅加达的摩天楼


下一篇:微信小程序全局变量(globalData)和缓存(StorageSync)的区别和具体用法