締まっていこう (AOJ1164)
たわみを無くすまで引っ張る・・・はせずに解きました.
解法はrngさんがこどふぉで記事に書いているとおりです.
しかし実装の細かい部分が結構たいへんだった.
まず,始点,終点をどう扱うか.ピンの点と同様に扱おうとすると,上をとおるか下をとおるかみたいなのの判定の時に飛ばさなきゃいけなくてちょっと面倒.別扱いにしても,長さ求めるDPの時にアクセスしにくくて面倒.
結局長さを求めるのをcalclen(始点,終点,半直線のidのvector)にすることで適当にやった.
こういうの短時間で綺麗に書くのはなかなか難しいですね・・・
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; typedef double D; typedef complex<D> P; int K,N; P ps[100],as[100]; bool up(P s,P t,P p){ //line over point D sx=s.real(),tx=t.real(),sy=s.imag(),ty=t.imag(),x=p.real(),y=p.imag(); D ly=sy+(ty-sy)/(tx-sx)*(x-sx); return ly>y; } void addpath(vector<int>& vc,P s,P t){ vector<int> ad; D sx=s.real(),tx=t.real(),sy=s.imag(),ty=t.imag(); bool sw=0; if(sx>tx){ sw=1; swap(sx,tx); swap(sy,ty); } rep(i,N){ D x=as[i].real(),y=as[i].imag(); if(sx<x&&x<tx){ if(up(s,t,as[i])) ad.pb(i*2); else ad.pb(i*2+1); } } if(sw) reverse(all(ad)); vc.insert(vc.end(),all(ad)); } bool cancel(vector<int>& vc){ bool update=0; int A=vc.size(); vector<bool> gomi(A,0); rep(i,A-1){ if(vc[i]==vc[i+1]){ gomi[i]=gomi[i+1]=1; update=1; i++; } } vector<int> nvc; rep(i,A) if(!gomi[i]) nvc.pb(vc[i]); vc=nvc; return update; } P point(int id){ return as[id/2]; } D calclen(P S,P T,vector<int>& vc){ // show(S); // show(T); int A=vc.size(); // show(A); // for(int v:vc) cout<<v<<" "; // puts(""); D dp[110]; rep(i,A+2) dp[i]=1e9; dp[0]=0; rep(i,A+1){ P t=(i==A?T:point(vc[i])); rep(j,i+1){ P s=(j==0?S:point(vc[j-1])); bool ok=1; for(int k=j;k<i;k++){ if(up(s,t,point(vc[k]))==(vc[k]&1)){ ok=0; break; } } if(ok) chmin(dp[i+1],dp[j]+abs(s-t)); } } return dp[A+1]; } int main(){ while(true){ cin>>K>>N; if(K==0) break; rep(i,K){ D x,y; cin>>x>>y; ps[i]=P(x,y)*polar(1.0,1.0); } rep(i,N){ D x,y; cin>>x>>y; as[i]=P(x,y)*polar(1.0,1.0); } rep(i,N-1) rep(j,N-1) if(as[j].real()>as[j+1].real()) swap(as[j],as[j+1]); vector<int> vc; rep(i,K-1) addpath(vc,ps[i],ps[i+1]); while(cancel(vc)); D ans=0; int M=vc.size(); int l=-1; for(int r=1;r<=M;r++){ if(r==M||(vc[r]^vc[r-1])==1){ vector<int> tmp; P s,t; if(l==-1) s=ps[0]; else s=point(vc[l]); if(r==M) t=ps[K-1]; else t=point(vc[r]); if(r==M) r++; for(int i=l+1;i<r-1;i++) tmp.pb(vc[i]); ans+=calclen(s,t,tmp); // show(calclen(s,t,tmp)); l=r; } } printf("%.12f\n",ans); } }