#include<bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
using Real=double;
const Real EPS=1e-8;
const Real PI=acos(-1.0);
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;
if(cross(b,c)<-EPS)return CLOCKWISE;
if(dot(b,c)<0)return ONLINE_BACK;
if(norm(b)<norm(c))return ONLINE_FRONT;
return ON_SEGMENT;
}
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;
}
class shortest_path{
public:
explicit shortest_path(int n):vertex(n),INF((double)1e9){
v1.resize(static_cast<unsigned long>(vertex));
}
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;
}
void add_edge(int from,int to,double cost){
v1[from].push_back({to,cost});
}
void add_edge_(int from,int to,ll cost){
v2[from][to]=cost;
}
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;
}
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);
}
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);
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);
if(!intersect(s1,aa)){
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);
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)){
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やるだけ。