#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <iomanip>
using namespace std;
/**
In loc sa incerca sa simulam traversarea robotului printre obstacole vom
reduce robotul la un punct. Acest procedeu se poate folosi deoarece robotul
nu se poate roti. Acum pentru a mari obstacolele ne uitam pentru fiecare obstacol in
ce loc o sa apara punctul de referinta ( 0 ) daca translam robotul din fiecare
punct al lui pe fiecare punct al obstacolului. Dupa ce avem aceste locuri geometrice
vom face un convex hull pentru a obtine noile obstacole.
Dupa ce avem aceste obstacole contruite o sa contruim un graf cu costuri pe care vom
rula un algoritm de drum minim. Acest graf va avea ca noduri fiecare punct din noile
obstacole ( + punctul de start si de sorire ) si vor exista muchii intre 2 puncte daca
aceste muchii nu se intersecteaza cu interiorul unui poligon. Vom verifica fiecare poligon
pe rand.
Pentru un poligon trebuie sa avem in vedere si cazurile in care dreapta coincide cu o dreapta
din poligon ( un e intersectie ) , un punct e in interiorul poligonului , 2 puncte sunt pe segmente
diferite. La final o sa intersectam dreapta cu toate segmentele poligonului si numaram intersectiile.
Daca acest numar e mai mare ca 1 , atunci avem intersectare.
*/
ifstream F("robot.in");
ofstream G("robot.out");
const double eps = 1e-9;
const int infi = 1<<30;
const int debuging = 0;
#define x first
#define y second
typedef pair<int,int> pi;
typedef pair<double,double> pd;
pi finish;
vector<pi> robot;
vector< vector<pi> > obstacle;
int ecu(pi A,pi B,pi C)
{
int a = A.y - B.y;
int b = B.x - A.x;
int c = - A.y * B.x + B.y * A.x;
int d = a * C.x + b * C.y + c;
return d > 0 ? 1 : ( d < 0 ? -1 : 0 );
}
int segment(pi A,pi B,pi C)
{
if ( ecu(A,B,C) ) return 0;
if ( min(A.x,B.x) > C.x || C.x > max(A.x,B.x) ) return 0;
if ( min(A.y,B.y) > C.y || C.y > max(A.y,B.y) ) return 0;
return 1;
}
void print_vector(vector<pi> V)
{
if ( debuging == 0 ) return;
G<<"debug: ";
for (vector<pi>::iterator it=V.begin();it!=V.end();++it)
G<<'('<<it->x<<","<<it->y<<") ";
G<<"\n";
}
void cprint_vector(vector<pi> V)
{
if ( debuging == 0 ) return;
cout<<"debug: ";
for (vector<pi>::iterator it=V.begin();it!=V.end();++it)
cout<<'('<<it->x<<","<<it->y<<") ";
cout<<"\n";
}
void print_array(double A[],int sz)
{
if ( debuging == 0 ) return;
G<<"debug: ";
for (int i=0;i<sz;++i)
{
if ( max(A[i]-infi,infi-A[i]) < eps ) G<<"infi "; else
G<<fixed<<setprecision(2)<<A[i]<<" ";
}
G<<"\n";
}
void read()
{
int N=0,M=0;
F>>N;
for (int i=1,x,y;i<=N;++i)
{
F>>x>>y;
robot.push_back( make_pair(x,y) );
}
F>>M;
for (int i=1;i<=M;++i)
{
vector<pi> act;
F>>N;
for (int j=1,x,y;j<=N;++j)
{
F>>x>>y;
act.push_back( make_pair(x,y) );
}
obstacle.push_back( act );
}
F>>finish.x>>finish.y;
}
pi trans(pi a,pi t,pi o)
{
return make_pair( a.x - o.x + t.x , a.y - o.y + t.y );
}
void convex_hull(vector<pi>& A)
{
sort(A.begin(),A.end());
A.erase( unique( A.begin(),A.end() ) , A.end() );
vector<pi> out;
vector<pi> stack;
int N = A.size();
for (int i=0;i<N;++i)
if ( ecu(A[0],A[N-1],A[i]) >= 0 )
{
if ( stack.size() > 1 )
while ( ecu( stack[stack.size()-2] , A[i] , stack[stack.size()-1] ) <= 0 )
{
stack.pop_back();
if ( stack.size() < 2 ) break;
}
stack.push_back(A[i]);
cprint_vector(stack);
}
while ( !stack.empty() )
{
stack.pop_back();
if ( !stack.empty() )
out.push_back( stack.back() );
}
for (int i=N-1;i>=0;--i)
if ( ecu(A[N-1],A[0],A[i]) >= 0 )
{
if ( stack.size() > 1 )
while ( ecu( stack[stack.size()-2] , A[i] , stack[stack.size()-1] ) <= 0 )
{
stack.pop_back();
if ( stack.size() < 2 ) break;
}
stack.push_back(A[i]);
if ( debuging ) cprint_vector(stack);
}
while ( !stack.empty() )
{
stack.pop_back();
if ( !stack.empty() )
out.push_back( stack.back() );
}
A = out;
}
void expand()
{
sort(robot.begin(),robot.end());
for (size_t i=0;i<obstacle.size();++i)
{
int size = obstacle[i].size();
for (int j=0;j<size;++j)
for (size_t k=0;k<robot.size();++k)
obstacle[i].push_back( trans(obstacle[i][j],robot[0],robot[k]) );
convex_hull( obstacle[i] );
if ( debuging ) print_vector( obstacle[i] );
}
}
void placef()
{
int miny = robot[0].y;
for (size_t i=1;i<robot.size();++i)
miny = min(miny,robot[i].y);
finish.y += robot[0].y-miny;
}
double dist(pi A,pi B)
{
return sqrt( (A.x-B.x) * (A.x-B.x) + (A.y-B.y) * (A.y-B.y) );
}
int next(int i,int s)
{
return i+1 < s ? i+1 : 0;
}
int cross(pi a,pi b)
{
return a.x * b.y - a.y * b.x;
}
int area(vector<pi> v)
{
int out = 0;
for (size_t i=0;i<v.size()-1;++i)
out += cross(v[i],v[i+1]);
out = max(out,-out);
return out;
}
int tarea(pi A,pi B,pi C)
{
int out = cross(A,B) + cross(B,C) + cross(C,A);
out = max(out,-out);
return out;
}
int parea(vector<pi> v,pi a)
{
int out = 0;
for (size_t i=0;i<v.size()-1;++i)
out += tarea(v[i],v[i+1],a);
return out;
}
pd internow;
int int2(pi A,pi B,pi C,pi D)
{
double a1 = A.y - B.y;
double b1 = B.x - A.x;
double c1 = - A.y * B.x + B.y * A.x;
double a2 = C.y - D.y;
double b2 = D.x - C.x;
double c2 = - C.y * D.x + D.y * C.x;
double d = a1*b2 - b1*a2;
if ( d == 0 )
return 0;
else
{
internow = make_pair( (b2*c1-b1*c2)/d , (a1*c2-a2*c1)/d );
return ecu(C,B,A)*ecu(D,B,A)<=0 && ecu(A,C,D)*ecu(B,C,D)<=0;
}
}
bool intersection(pi A,pi B,vector<pi> V)
{
int N = V.size();
V.push_back(V[0]);
for (int i=0;i<N;++i)
if ( ecu(A,V[i],V[i+1]) == 0 && ecu(B,V[i],V[i+1]) == 0 )
return 0;
int a=0,b=0;
for (int i=0;i<N;++i)
{
if ( segment(V[i],V[i+1],A) ) a = 1;
if ( segment(V[i],V[i+1],B) ) b = 1;
}
if ( a && b ) return 1;
int area_v = area(V);
int area_a = parea(V,A);
int area_b = parea(V,B);
if ( area_v == area_a && a == 0 ) return 1;
if ( area_v == area_b && b == 0 ) return 1;
vector<pd> inter;
for (int i=0;i<N;++i)
if ( int2(A,B,V[i],V[i+1]) )
inter.push_back( internow );
sort(inter.begin(),inter.end());
inter.erase(unique(inter.begin(),inter.end()),inter.end());
return inter.size() > 1;
}
double distancee(pi A,pi B)
{
if ( A == B ) return 0;
double out = dist(A,B);
for (vector< vector<pi> >::iterator vect=obstacle.begin();vect!=obstacle.end();++vect)
if ( intersection(A,B,*vect) )
return infi;
return out;
}
void solve()
{
vector<pi> points;
points.push_back( robot[0] );
for (vector< vector<pi> >::iterator vect=obstacle.begin();vect!=obstacle.end();++vect)
for (vector<pi>::iterator it=vect->begin();it!=vect->end();++it)
points.push_back(*it);
points.push_back( finish );
int N = points.size();
double cost[N+10][N+10];
for (int i=0;i<N;++i)
for (int j=0;j<N;++j)
cost[i][j] = distancee(points[i],points[j]);
for (int i=0;i<N;++i)
print_array( cost[i],N );
double d[N+10];
for (int i=0;i<N;++i)
d[i] = infi;
d[0] = 0;
queue<int> Q;
Q.push(0);
if ( debuging ) G<<"\n";
while ( Q.size() )
{
int node = Q.front();
Q.pop();
for (int i=0;i<N;++i)
if ( d[node] + cost[node][i] < d[i] - eps )
{
Q.push( i );
d[i] = d[node] + cost[node][i];
}
print_array(d,N);
}
G<<fixed<<setprecision(3)<<d[N-1]<<'\n';
}
int main()
{
read();
expand();
placef();
solve();
}