AOJ 1139: Earth Observation with a Mobile Robot Team

この記事は、AOJ-ICPC Advent Calendarの記事です。

古い問題らしい癖問。
妙にやりにくい幾何パート、妙にやりにくいグラフパート、そしてそれらに劣らないほどのやりにくさを誇る入力形式。
無駄に大変だけどなんとかはなった。言われたとおりに実装すれば時間制限は全然問題ない。

本当に書きにくい問題だったけどコンパイルを通してから直接1発ACが取れてしまった。
さすがに幾何実装の

って感じがした。

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
using namespace std;
const double EPS = 1e-10;
const double INF = 1e+10;
const double PI = acos(-1);

char in[100];
string name[110];
vector<Pt>v[110];
vector<double>t[110];
vector<pair<double,pair<int,int> > >ev;
vector<string>ans;
int ret[110];
int g[110][110];
int bfs[110];
int main(){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    scanf("%s",in);
    int na,nb,nc;
    while(a){
        double r=(double)c;
        for(int i=0;i<110;i++){
            v[i].clear();
            t[i].clear();
        }
        for(int i=0;i<a;i++){
            name[i]=in;
            while(1){
                int chk=scanf("%s",in);
                if(chk==-1)break;
                if('a'<=in[0]&&in[0]<='z')break;
                int tmp,x,y;
                sscanf(in,"%d",&tmp);
                na=tmp;
                t[i].push_back((double)tmp);
                scanf("%d%d",&x,&y);
                nb=x;nc=y;
                v[i].push_back(Pt((double)x,(double)y));
            }
            if(i==a-1){
                t[i].pop_back();
                v[i].pop_back();
            }
        }
        ev.clear();
        for(int i=0;i<a;i++)for(int j=i+1;j<a;j++){
            if((v[i][0]-v[j][0]).ABS()<r)ev.push_back(make_pair(0,make_pair(i,j)));
            int L=1;
            int R=1;
            Pt at=v[i][0]-v[j][0];
            while(1){
                double left=max(t[i][L-1],t[j][R-1]);
                double right=min(t[i][L],t[j][R]);
                Pt tv=v[i][L]-v[j][R];
                if(iCS(Pt(0,0),r,at,at+tv*(right-left))){
                    pair<Pt,Pt> it=pCL(Pt(0,0),r,at,at+tv*(right-left));
                    if(iSP(at,it.first,at+tv*(right-left))==2||(at+tv*(right-left)-it.first).ABS()<EPS){
                        ev.push_back(make_pair(left+(it.first-at).ABS()/(tv.ABS()),make_pair(i,j)));
                    }
                    if(iSP(at,it.second,at+tv*(right-left))==2||(at+tv*(right-left)-it.second).ABS()<EPS){
                        ev.push_back(make_pair(left+(it.second-at).ABS()/(tv.ABS()),make_pair(i,j)));
                    }
                }
                at=at+tv*(right-left);
                if(L==t[i].size()-1&&R==t[j].size()-1)break;
                else if(L==t[i].size()-1)R++;
                else if(R==t[j].size()-1)L++;
                else if(t[i][L]>t[j][R]+EPS)R++;
                else if(t[i][L]+EPS<t[j][R])L++;
                else {L++;R++;}
            }
        }
        std::sort(ev.begin(),ev.end());
        for(int i=0;i<a;i++)ret[i]=0;
        ret[0]=1;
        for(int i=0;i<a;i++)for(int j=0;j<a;j++)g[i][j]=0;
        for(int i=0;i<ev.size();i++){
            g[ev[i].second.first][ev[i].second.second]^=1;
            if(g[ev[i].second.first][ev[i].second.second]&&ret[ev[i].second.first]+ret[ev[i].second.second]){
                queue<int>Q;
                for(int j=0;j<a;j++)bfs[j]=0;
                Q.push(ev[i].second.first);
                bfs[ev[i].second.first]=1;
                while(Q.size()){
                    int at=Q.front();
                    Q.pop();
                    for(int j=0;j<a;j++){
                        if(!bfs[j]&&(g[at][j]||g[j][at])){
                            bfs[j]=1;Q.push(j);
                        }
                    }
                }
                for(int j=0;j<a;j++)if(bfs[j])ret[j]=1;
            }
        }
        ans.clear();
        for(int i=0;i<a;i++)if(ret[i])ans.push_back(name[i]);
        std::sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();i++)printf("%s\n",ans[i].c_str());
        a=na;b=nb;c=nc;
    }
}