この記事は、AOJ-ICPC Advent Calendarの記事です。
二つのスポットライトを選んで、いる辺が変わるタイミングを列挙してソートしてして頂点求めて…、というのが面倒だが、そこまでやったら三分探索で距離はわかるし、二つのスポットライトの関係性が分かったらグラフパートは皆無なので、そこまでハードではない。
いわゆる頭を使わない幾何実装で、コード長とかのわりにやりやすい。
#include<stdio.h> #include<algorithm> #include<math.h> #include<vector> using namespace std; const double EPS = 1e-10; const double INF = 1e+10; const double PI = acos(-1); double r[110]; vector<Pt>p[110]; double len[110]; int UF[110]; int FIND(int a){ if(UF[a]<0)return a;return UF[a]=FIND(UF[a]); } void UNION(int a,int b){ a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a; } pair<double,int>ev[200]; int cs[210]; int ce[210]; int main(){ int a; double sx,sy,ex,ey; scanf("%d%lf%lf%lf%lf",&a,&sx,&sy,&ex,&ey); Pt S=Pt(sx,sy); Pt E=Pt(ex,ey); for(int i=0;i<110;i++)UF[i]=-1; for(int i=0;i<a;i++){ scanf("%lf",r+i); int b;scanf("%d",&b); for(int j=0;j<b;j++){ double x,y; scanf("%lf%lf",&x,&y); p[i].push_back(Pt(x,y)); } p[i].push_back(p[i][0]); for(int j=0;j<b;j++)len[i]+=(p[i][j+1]-p[i][j]).ABS(); } for(int i=0;i<a;i++){ for(int j=i+1;j<a;j++){ double now=0; for(int k=0;k<p[i].size();k++){ ev[k]=make_pair(now*10000/len[i],0); if(k<p[i].size()-1)now+=(p[i][k+1]-p[i][k]).ABS(); } now=0; for(int k=0;k<p[j].size();k++){ ev[p[i].size()+k]=make_pair(now*10000/len[j],1); if(k<p[j].size()-1)now+=(p[j][k+1]-p[j][k]).ABS(); } int n=p[i].size()+p[j].size(); std::sort(ev,ev+n); int na=-1; int nb=-1; double pa=0; double pb=0; double ta=0; double tb=0; bool ok=false; // printf("%d %d: %d\n",i,j,n); for(int k=0;k<n-1;k++){ if(ev[k].second==0){ na++; if(na&&na<p[i].size()){ pa+=ta; } ta=(p[i][na+1]-p[i][na]).ABS()*10000/len[i]; }else{ nb++; if(nb&&nb<p[j].size()){ pb+=tb; } tb=(p[j][nb+1]-p[j][nb]).ABS()*10000/len[j]; } // printf("%f %d\n",ev[k].first,ev[k].second); if(ev[k+1].first-ev[k].first>EPS){ double left=ev[k].first; double right=ev[k+1].first; double il=(p[i][na+1]-p[i][na]).ABS()*10000; double jl=(p[j][nb+1]-p[j][nb]).ABS()*10000; double D=999999999; for(int l=0;l<50;l++){ double m1=(left*2+right)/3; double m2=(left+right*2)/3; double ar,br; double d1,d2; Pt ap,bp; ar=(m1-pa)/ta; ap=p[i][na]+(p[i][na+1]-p[i][na])*ar; br=(m1-pb)/tb; bp=p[j][nb]+(p[j][nb+1]-p[j][nb])*br; d1=(ap-bp).ABS(); ar=(m2-pa)/ta; ap=p[i][na]+(p[i][na+1]-p[i][na])*ar; br=(m2-pb)/tb; bp=p[j][nb]+(p[j][nb+1]-p[j][nb])*br; d2=(ap-bp).ABS(); if(d1<d2)right=m2; else left=m1; if(min(d1,d2)<r[i]+r[j]){ ok=true; } D=min(D,min(d1,d2)); } // printf("%d %d %d %d %d: %f %f\n",i,j,k,na,nb,D,left); } } if(ok)UNION(i,j); } } for(int i=0;i<a;i++){ for(int j=0;j<p[i].size()-1;j++){ if(dSP(p[i][j],p[i][j+1],S)<r[i])cs[i]=1; if(dSP(p[i][j],p[i][j+1],E)<r[i])ce[i]=1; } } bool ret=false; for(int i=0;i<a;i++){ //printf("%d %d %d\n",FIND(i),cs[i],ce[i]); } for(int i=0;i<a;i++){ for(int j=0;j<a;j++){ if(cs[i]&&ce[j]&&FIND(i)==FIND(j))ret=true; } } if(ret)printf("Yes\n"); else printf("No\n"); }
