静かで孤独な日記

のんびりたまに

AOJ 2334 Roads on Towns

#include<bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;

//幾何ライブラリ
//ほぼ、https://ei1333.github.io/algorithm/geometry_new.html からパクりました

using Real=double;//問題によってはlong double に変更してください
const Real EPS=1e-8;//問題によって値を変更してください
const Real PI=acos(-1.0);//3.141592653589793238...
inline bool eq(Real a,Real b){return fabs(b-a)<EPS;}//誤差を考慮した等価判定
static const int COUNTER_CLOCKWISE=1;
static const int CLOCKWISE=-1;
static const int ONLINE_BACK=2;
static const int ONLINE_FRONT=-2;
static const int ON_SEGMENT=0;
typedef complex<Real> Point;//点

//直線
struct Line{
    Point p1,p2;
    Line()= default;
    Line(Point a,Point b):p1(a),p2(b){};
};

//線分
struct Segment:Line{
    Segment()= default;
    Segment(Point a,Point b):Line(a,b){}
};

//点同士の大小比較
namespace std {
    bool operator<(const Point &a, const Point &b) {
        return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
    }
}

//外積
Real cross(const Point& a,const Point& b){
    return a.real()*b.imag()-a.imag()*b.real();
}

//内積
Real dot(const Point& a,const Point& b){
    return a.real()*b.real()+a.imag()*b.imag();
}


int ccw(Point a,Point b,Point c){
    b=b-a;c=c-a;
    if(cross(b,c)>EPS)return COUNTER_CLOCKWISE;//1
    if(cross(b,c)<-EPS)return CLOCKWISE;//-1
    if(dot(b,c)<0)return ONLINE_BACK;//2
    if(norm(b)<norm(c))return ONLINE_FRONT;//-2
    return ON_SEGMENT;//0
}

bool intersect(const Segment& s,const Segment& t){
    return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2)<=0 && ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2)<=0;
}

//Shortest_Path
//グラフの最短距離を求めるアルゴリズムを3種類持っているクラスです
class shortest_path{
public:
    
    //dijkstra法とBellman_Ford法を使うときは、このコンストラクタを使ってください
    explicit shortest_path(int n):vertex(n),INF((double)1e9){
        v1.resize(static_cast<unsigned long>(vertex));
    }
    
    //Warshall_Floyd法を使うときは、こちらのコンストラクタを使ってください
    shortest_path(int n,double inf):vertex(n),INF(inf){
        v2.resize(static_cast<unsigned long>(vertex));
        for(int i=0;i<vertex;i++)v2[i].resize(static_cast<unsigned long>(vertex));
        for(int i=0;i<vertex;i++){
            for(int j=0;j<vertex;j++){
                v2[i][j]=INF;
            }
        }
        for(int i=0;i<vertex;i++)v2[i][i]=0;
    }
    
    //dijkstra法とBellman_Ford法専用のadd_edge(int from,int to,ll cost)です
    //コストcostの頂点fromから頂点toへの有向辺を追加するときadd_edge(int from,int to,ll cost)
    void add_edge(int from,int to,double cost){
        v1[from].push_back({to,cost});
    }
    
    //Warshall_Floyd法専用のadd_edge(int from,int to,ll cost)です
    //コストcostの頂点fromから頂点toへの有向辺を追加するときadd_edge(int from,int to,ll cost)
    void add_edge_(int from,int to,ll cost){//warshall_floyd
        v2[from][to]=cost;
    }
    
    //Dijkstra法です
    //各頂点への距離が格納されたvector<ll>が求まります
    //負のコストの辺がある場合は使えません
    //start地点の頂点番号を引数に入れてください
    vector<double> dijkstra(unsigned int start){
        vector<double> d(static_cast<unsigned long>(vertex),INF);
        priority_queue<pair<double,int> > q;
        d[start]=0;
        q.push({0,start});
        while(!q.empty()){
            int now=q.top().se;
            double now_cost=-q.top().fi;
            q.pop();
            if(d[now]<now_cost)continue;
            for (auto &i : v1[now]) {
                if(d[i.fi]>now_cost+ i.se){
                    d[i.fi]=now_cost+ i.se;
                    q.push({-d[i.fi], i.fi});
                }
            }
        }
        return d;
    }
    
    //Warshall_Floyd法です
    //各頂点への距離が格納されたvector<ll>と閉路があるかどうかの情報の2つのtupleが返されます
    //閉路があるとき、返り値はtrueです
    tuple<vector<vector<ll> >,bool> warshall_floyd(){
        for(int k=0;k<vertex;k++){
            for(int i=0;i<vertex;i++){
                if(v2[i][k]==INF)continue;
                for(int j=0;j<vertex;j++){
                    if(v2[k][j]==INF)continue;
                    v2[i][j]=min(v2[i][j],v2[i][k]+v2[k][j]);
                }
            }
        }
        bool is_negative_cycle=false;
        for(int i=0;i<vertex;i++){
            if(v2[i][i]<0)is_negative_cycle=true;
        }
        return make_tuple(v2,is_negative_cycle);
    }

    //Bellman_Ford法です
    //各頂点への距離が格納されたvector<ll>と閉路があるかどうかの情報の2つのtupleが返されます
    //閉路があるとき、返り値はtrueです
    //start地点の頂点番号を引数に入れてください
    tuple<vector<ll>,bool> bellman_ford(int start){
        vector<ll> d(static_cast<unsigned long>(vertex),INF);
        d[start]=0;
        bool is_negative_cycle=false;
        for(int i=0;i<vertex;i++){
            bool update= false;
            for(int j=0;j<vertex;j++){
                if(d[j]==INF)continue;
                for(int k=0;k<(int)v1[j].size();k++){
                    if(d[v1[j][k].fi]>d[j]+v1[j][k].se){
                        d[v1[j][k].fi]=d[j]+v1[j][k].se;
                        update= true;
                    }
                }
            }
            if(i==vertex-1 && update)is_negative_cycle=true;
            else if(!update)break;
        }
        return make_tuple(d,is_negative_cycle);
    }
private:
    double INF;
    int vertex;
    vector<vector<pair<int,double> > > v1;
    vector<vector<ll> > v2;
};

int na,nb;
double xa[1001],ya[1001],xb[1001],yb[1001];

int main(){
  int na,nb;
  cin>>na>>nb;
  for(int i=0;i<na;i++){
    cin>>xa[i]>>ya[i];
  }
  for(int i=0;i<nb;i++){
    cin>>xb[i]>>yb[i];
  }
  Point tmp(xb[0],yb[0]);
  Point tmp2(xb[1],yb[1]);
  Segment s1(tmp,tmp2);
  shortest_path sp1(na);
  //cout<<1<<endl;
  for(int i=0;i<na;i++){
    for(int j=i+1;j<na;j++){
      Point a(xa[i],ya[i]);
      Point b(xa[j],ya[j]);
      Segment aa(a,b);
      //cout<<aa.p1<<" "<<aa.p2<<endl;
      if(!intersect(s1,aa)){
        //cout<<i<<"--"<<j<<endl;
        sp1.add_edge(i,j,sqrt((xa[i]-xa[j])*(xa[i]-xa[j])+(ya[i]-ya[j])*(ya[i]-ya[j])));
        sp1.add_edge(j,i,sqrt((xa[i]-xa[j])*(xa[i]-xa[j])+(ya[i]-ya[j])*(ya[i]-ya[j])));
      }
    }
  }
  vector<double> di1=sp1.dijkstra(0);
  double ans;
  if(di1[1]!=1e9){
    ans=di1[1]+getDistance(tmp,tmp2);
  }else{
    ans=inf;
  }
  Point tmp3(xa[0],ya[0]);
  Point tmp4(xa[1],ya[1]);
  Segment s2(tmp3,tmp4);
  shortest_path sp2(nb);
  //cout<<2<<endl;
  for(int i=0;i<nb;i++){
    for(int j=i+1;j<nb;j++){
      Point a(xb[i],yb[i]);
      Point b(xb[j],yb[j]);
      Segment aa(a,b);
      if(!intersect(s2,aa)){
        //cout<<i<<"--"<<j<<endl;
        sp2.add_edge(i,j,sqrt((xb[i]-xb[j])*(xb[i]-xb[j])+(yb[i]-yb[j])*(yb[i]-yb[j])));
        sp2.add_edge(j,i,sqrt((xb[i]-xb[j])*(xb[i]-xb[j])+(yb[i]-yb[j])*(yb[i]-yb[j])));
      }
    }
  }
  vector<double> di2=sp2.dijkstra(0);
  if(di2[1]!=inf){
    ans=min(ans,di2[1]+getDistance(tmp3,tmp4));
  }else{
    ans=min(ans,inf);
  }
  if(ans!=inf){
    printf("%.12f\n",ans);
  }else{
    cout<<-1<<endl;
  }
  return 0;
}
  • 街の数が1000くらいだからO(n^2)解があるだろうなんて考えたら簡単に思いついた。
  • 交差判定して交差してなかったら変を追加。
  • 変を追加したら0から1への最短距離求めるためにdijkstraやるだけ。