#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
ifstream fin ("robot.in"); ofstream fout ("robot.out");
const int nmax = 25;
const int pmax = 1000;
struct pct {
double x, y;
pct () {}
pct (double _x, double _y) {
x = _x, y = _y;
}
pct operator + (const pct &shp) const {
return pct(x + shp.x, y + shp.y);
}
pct operator - (const pct &shp) const {
return pct(x - shp.x, y - shp.y);
}
pct operator * (const pct &shp) const {
return pct (x * shp.x - y * shp.y, y * shp.x + x * shp.y);
}
};
pct conj (pct a) {
return pct(a.x, -a.y);
}
double real (pct a) {
return a.x;
}
double imag (pct a) {
return a.y;
}
struct Heap_node {
int x; double val;
Heap_node () {}
Heap_node (int _x, double _val) {
x = _x, val = _val;
}
bool operator < (const Heap_node &shp) const {
return val > shp.val;
}
};
priority_queue< Heap_node > heap;
bool gata[pmax + 1];
double d[pmax + 1];
int m, nrnoduri;
pct destinatie, centru_obs;
pct cine[pmax + 1];
vector< pct > robot;
vector< pct > obs[nmax + 1];
vector< pair<int, double> > g[pmax + 1];
double dot (pct a, pct b) {
return real(conj(a) * b);
}
double cross (pct a, pct b) {
return imag(conj(a) * b);
}
double det (pct a, pct b, pct c) {
return cross(b - a, c - a);
}
bool cmp (pct a, pct b) {
if (real(a) == real(b) && real(a) == real(centru_obs)) {
return imag(a) < imag(b);
}
return det(centru_obs, a, b) > 0;
}
vector< pct > mareste(vector< pct > poli) {
vector< pct > ans;
for (auto i : poli) {
for (auto j : robot) {
ans.push_back(robot[ 0 ] + i - j);
}
}
for (int i = 1; i < (int)ans.size(); ++ i) {
if (real(ans[ i ]) < real(ans[ 0 ])) {
swap(ans[ 0 ], ans[ i ]);
}
if (real(ans[ i ]) == real(ans[ 0 ]) && imag(ans[ i ]) < imag(ans[ 0 ])) {
swap(ans[ 0 ], ans[ i ]);
}
}
centru_obs = *ans.begin();
sort(ans.begin() + 1, ans.end(), cmp);
vector< pct > stk;
int sz = 0;
for (auto i : ans) {
while (sz >= 2 && det(stk[sz - 2], stk[sz - 1], i) <= 0) {
-- sz;
stk.pop_back();
}
++ sz;
stk.push_back( i );
}
//for (auto i : stk)
// fout << i << "\n";
return stk;
}
void citire () {
int n;
fin >> n;
double px = INFINITY, py = INFINITY;
for (int i = 1; i <= n; ++ i) {
double x, y;
fin >> x >> y;
robot.push_back(pct(x, y));
px = min(px, x);
py = min(py, y);
}
fin >> m;
for (int i = 1; i <= m; ++ i) {
int nrp;
fin >> nrp;
vector< pct > obs_init;
for (int j = 1; j <= nrp; ++ j) {
double x, y;
fin >> x >> y;
obs_init.push_back(pct(x, y));
}
obs[ i ] = mareste( obs_init );
}
double dx, dy;
fin >> dx >> dy;
dx += real(robot[ 0 ]) - px;
dy += imag(robot[ 0 ]) - py;
destinatie = pct(dx, dy);
}
bool intersect (pct a, pct b, pct x, pct y) {
if (cross(b - a, y - x) == 0) /// daca sunt paralele nu conteaza, chiar daca se intersecteaza
return 0;
return det(a, b, x) * det(a, b, y) < 0 && det(x, y, a) * det(x, y, b) < 0;
}
bool invalid (pct u) {
for (int i = 1; i <= m; ++ i) {
double ariet = 0, s = 0;
bool marg = 0;
for (int j = 0; j < (int)obs[ i ].size(); ++ j) {
pct nxt = obs[ i ][ 0 ];
if (j + 1 < (int)obs[ i ].size())
nxt = obs[ i ][j + 1];
ariet += cross(obs[ i ][ j ], nxt);
double tr = fabs(det(obs[ i ][ j ], nxt, u));
s += tr;
if (tr == 0)
marg = 1;
}
if (fabs(ariet) == s && marg == 0)
return 1;
}
return 0;
}
void fa_graf () {
cine[ 0 ] = robot[ 0 ];
++ nrnoduri;
for (int i = 1; i <= m; ++ i) {
for (auto j : obs[ i ]) {
cine[ nrnoduri ++ ] = j;
}
}
cine[ nrnoduri ++ ] = destinatie;
for (int i = 0; i < nrnoduri; ++ i) {
for (int j = i + 1; j < nrnoduri; ++ j) {
bool ok = 1;
for (int p = 1; p <= m && ok; ++ p) {
for (int x = 0; x < (int)obs[ p ].size() && ok; ++ x) {
for (int y = x + 1; y < (int)obs[ p ].size() && ok; ++ y) {
if (intersect(cine[ i ], cine[ j ], obs[ p ][ x ], obs[ p ][ y ])) {
ok = 0;
}
}
}
}
if (ok == 1 && !invalid(cine[ i ]) && !invalid(cine[ j ])) {
double dist = sqrt(dot(cine[ i ] - cine[ j ], cine[ i ] - cine[ j ]));
g[ i ].push_back(make_pair(j, dist));
g[ j ].push_back(make_pair(i, dist));
}
}
}
}
void extinde (Heap_node u) {
for (auto i : g[ u.x ]) {
if (d[ i.first ] > d[ u.x ] + i.second) {
d[ i.first ] = d[ u.x ] + i.second;
heap.push(Heap_node(i.first, d[ i.first ]));
}
}
}
void dijkstra () {
for (int i = 0; i < pmax; ++ i) {
d[ i ] = INFINITY;
}
d[ 0 ] = 0;
heap.push(Heap_node(0, 0));
while (!heap.empty()) {
Heap_node u = heap.top();
heap.pop();
if (gata[ u.x ] == 1)
continue;
gata[ u.x ] = 1;
extinde( u );
}
}
int main () {
citire ();
fa_graf ();
dijkstra ();
if (d[nrnoduri - 1] == INFINITY) {
fout << "-1\n";
} else {
fout << setprecision( 6 ) << fixed;
fout << d[nrnoduri - 1] << "\n";
}
fin.close();
fout.close();
return 0;
}
Sarmasag Rares rares9301