#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
using ftype = double;
using ll = long long;
const int INF = 1e9;
const ftype EPS = 1e-4;
struct Point {
int x, y;
Point( int x = 0, int y = 0 ): x(x), y(y) {}
Point operator + ( const Point& that ) const { return Point(x + that.x, y + that.y); }
Point operator - ( const Point& that ) const { return Point(x - that.x, y - that.y); }
Point operator += ( const Point& that ) { return *this = *this + that; }
Point operator -= ( const Point& that ) { return *this = *this - that; }
bool operator == ( const Point& that ) const { return x == that.x && y == that.y; }
};
int sdet( const Point &a, const Point &b, const Point &c ) {
ll det = (a.x - b.x) * (ll)(a.y - c.y) - (a.y - b.y) * (ll)(a.x - c.x);
if( det < 0 ) return -1;
if( det > 0 ) return +1;
return 0;
}
using Poly = std::vector<Point>;
Poly hull_half( const std::vector<Point> &points, int sgn ) {
Poly ret;
for( Point P : points ){
while( ret.size() >= 2 && sdet( ret.end()[-2], ret.end()[-1], P ) * sgn <= 0 )
ret.pop_back();
ret.push_back( P );
}
return ret;
}
Poly hull( std::vector<Point> &points ) {
std::sort( points.begin(), points.end(), []( const Point &a, const Point &b ) -> bool {
if( a.x == b.x )
return a.y < b.y;
return a.x < b.x;
} );
Poly upper = hull_half( points, +1 );
Poly lower = hull_half( points, -1 );
upper.insert( upper.end(), lower.rbegin() + 1, lower.rend() - 1 );
return upper;
}
Poly enlarge_obstacle( const Poly &obs, const Poly &robot ) {
std::vector<Point> candidates;
for( Point V : obs )
for( Point V_rob : robot ){
// mutam V_rob peste V
// ne pasa unde ajunge punctul (0, 0)
// O + V_rob = V_rob
// O' + V_rob = V
candidates.push_back( V - V_rob );
}
return hull( candidates );
}
struct Seg {
Point a, b;
Seg(): a(), b() {}
Seg( Point a, Point b ): a(a), b(b) {}
ftype len() { return hypot( a.x - b.x, a.y - b.y ); }
};
template<typename T> bool in_box( T x, T y, const Seg& S ) {
if( x < S.a.x && x < S.b.x ) return false;
if( x > S.a.x && x > S.b.x ) return false;
if( y < S.a.y && y < S.b.y ) return false;
if( y > S.a.y && y > S.b.y ) return false;
if( hypot( x - S.a.x, y - S.a.y ) < EPS ) return false;
if( hypot( x - S.b.x, y - S.b.y ) < EPS ) return false;
return true;
}
bool in_box( const Point &P, const Seg& S ) {
return in_box( P.x, P.y, S );
}
// we want the INTERIORS to intersect
bool seg_intersect( const Seg &strips, const Seg &wing ) {
if( strips.a == strips.b ) return false;
if( wing.a == wing.b ) return false;
// printf( "strips = (%d %d) -- (%d %d)\n", strips.a.x, strips.a.y, strips.b.x, strips.b.y );
// printf( "wing = (%d %d) -- (%d %d)\n", wing.a.x, wing.a.y, wing.b.x, wing.b.y );
// intersectam dreptele
// Ax + By + C = 0
// Axa + Bya + C = 0
// Axb + Byb + C = 0
// A(xa - xb) + B(ya - yb) = 0
// A <- +(ya - yb)
// B <- -(xa - xb)
// C = -(ya - yb)xa + +(xa - xb)ya = -yaxa + ybxa + xaya - xbya
// C = ybxa - xbya
int stripsA = +(strips.a.y - strips.b.y);
int stripsB = -(strips.a.x - strips.b.x);
int stripsC = strips.b.y * strips.a.x - strips.a.y * strips.b.x;
int wingA = +(wing.a.y - wing.b.y);
int wingB = -(wing.a.x - wing.b.x);
int wingC = wing.b.y * wing.a.x - wing.a.y * wing.b.x;
if( stripsA * (ll)wingB == wingA * (ll)stripsB ){ // segmente paralele
// printf( "parallel\n" );
return false; // <----- (!!)
if( !(stripsA * (ll)wingC == wingA * (ll)stripsC && stripsB * (ll)wingC == wingB * (ll)stripsC) )
return false;
// segmentele au aceeasi dreapta suport
if( in_box( strips.a, wing ) ) return true;
if( in_box( strips.b, wing ) ) return true;
if( in_box( wing.a, strips ) ) return true;
if( in_box( wing.b, strips ) ) return true;
return false;
}
// sAx + sBy + sC = 0
// wAx + wBy + wC = 0
// -- eliminam x, y
// (wAsB - sAwB) * y + (wAsC - sAwC) = 0
// (wBsA - sBwA) * x + (wBsC - sBwC) = 0
ftype x_int = -(wingB * (ll)stripsC - stripsB * (ll)wingC) / (ftype)(wingB * (ll)stripsA - stripsB * (ll)wingA);
ftype y_int = -(wingA * (ll)stripsC - stripsA * (ll)wingC) / (ftype)(wingA * (ll)stripsB - stripsA * (ll)wingB);
// printf( "intersect (%.3lf %.3lf)\n", x_int, y_int );
return in_box( x_int, y_int, strips ) && in_box( x_int, y_int, wing );
}
std::vector<Seg> dangerous;
bool hits_interior( const Seg& proba ) {
for( Seg D : dangerous )
if( seg_intersect( D, proba ) ){
//printf( "true!! -- (%d %d) -- (%d %d) este rau\n", proba.a.x, proba.a.y, proba.b.x, proba.b.y );
return true;
}
return false;
}
namespace Graph {
std::vector<Point> points;
int n;
struct Edge {
int u;
ftype cost;
Edge( int u, ftype cost ): u(u), cost(cost) {}
};
// daca tot ai facut problema doar cu std::vector nu mai are rost sa schimbi acum
std::vector<std::vector<Edge>> adj;
// points[] si dangerous[] sunt calculate
void build() {
n = (int)points.size();
adj.resize( n );
for( int i = 0; i < n; i++ )
for( int j = i + 1; j < n; j++ ){
Seg S(points[i], points[j]);
if( !hits_interior( S ) ){
ftype cost = S.len();
adj[i].emplace_back( j, cost );
adj[j].emplace_back( i, cost );
}
}
}
ftype dijkstra( int src, int dest ) {
std::vector<ftype> dist(n, +INF);
std::priority_queue<std::pair<ftype, int>> pq;
pq.emplace( 0, src );
dist[src] = 0;
while( !pq.empty() ){
auto top = pq.top();
pq.pop();
int u = top.second;
if( -dist[u] != top.first ) // trebuie egalitate exacta, nu e nevoie de EPS
continue;
for( Edge e : adj[u] ){
if( dist[u] + e.cost < dist[e.u] ){
dist[e.u] = dist[u] + e.cost;
pq.emplace( -dist[e.u], e.u );
}
}
}
return dist[dest];
}
}
int main() {
FILE *fin = fopen( "robot.in", "r" );
FILE *fout = fopen( "robot.out", "w" );
Poly robot;
Point start(+INF, +INF);
{ // citim robotul
int n;
fscanf( fin, "%d", &n );
robot.reserve( n );
for( int i = 0; i < n; i++ ){
int x, y;
fscanf( fin, "%d%d", &x, &y );
robot.emplace_back( x, y );
start.x = std::min( start.x, x );
start.y = std::min( start.y, y );
}
// folosim conventia din enunt pentru pozitia robotului
for( Point &P : robot )
P -= start;
}
std::vector<Poly> obstacles;
{ // citim obstacolele
int m;
fscanf( fin, "%d", &m );
for( int i = 0; i < m; i++ ){
int siz;
fscanf( fin, "%d", &siz );
obstacles.emplace_back();
obstacles.back().reserve( siz );
for( int i = 0; i < siz; i++ ){
int x, y;
fscanf( fin, "%d%d", &x, &y );
obstacles.back().emplace_back( x, y );
}
obstacles.back() = enlarge_obstacle( obstacles.back(), robot );
}
}
{ // punem segmentele importante in dangerous[]
for( const Poly& obs : obstacles ){
int n = (int)obs.size();
for( int i = 0; i < n; i++ ){
dangerous.emplace_back( obs[i], obs[(i + 1) % n] );
dangerous.emplace_back( obs[i], obs[(i + 2) % n] );
}
}
}
Point finish;
fscanf( fin, "%d%d", &finish.x, &finish.y );
// printf( "drum: (%d %d) -- (%d %d)\n", start.x, start.y, finish.x, finish.y );
// hits_interior( Seg(start, finish) );
// printf( "------------------\n" );
int src = 0, dest = 1;
Graph::points.push_back( start );
Graph::points.push_back( finish );
for( const Poly& obs : obstacles )
for( Point P : obs )
Graph::points.push_back( P );
Graph::build();
ftype ret = Graph::dijkstra( src, dest );
if( ret < (ftype)(+INF) )
fprintf( fout, "%.2lf\n", ret );
else
fprintf( fout, "-1\n" );
fclose( fin );
fclose( fout );
return 0;
}