#include #include #include using namespace std; struct Point { double x; double y; // překlopení podle osy x Point flip() const { Point pt; pt.x = x; pt.y = -y; return pt; } // vždy chceme třídit horizontálně podle x, dále podle y bool operator< (const Point& pt) const { return x < pt.x || (x == pt.x && y < pt.y); } double distanceTo(const Point& p) const { return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y)); } }; typedef set PointMap; // uspořádaná množina bodu Point scanpt() { Point pt; double x, y; scanf("%lf %lf\n", &x, &y); pt.x = x; pt.y = y; return pt; } // Je směrnice (a -> p) větší než (a -> b) ? bool Above(Point p, Point a, Point b) { return (p.y - a.y) * (b.x - a.x) > (b.y - a.y) * (p.x - a.x); } double AddPoint(PointMap& envelope, Point pt) { PointMap::iterator rightNeighbour = envelope.lower_bound(pt); PointMap::iterator insertPoint = envelope.end(); double delta = 0; if(rightNeighbour == envelope.end()) // nový pravý okraj? { PointMap::iterator leftNeighbour = envelope.end(); leftNeighbour--; delta = leftNeighbour->distanceTo(pt); insertPoint = envelope.insert(pt).first; } else if(rightNeighbour == envelope.begin()) // nový levý okraj? { if(rightNeighbour->x == pt.x) // tzn. tento bod je přímo pod původním levým okrajem return 0; // zahodím ho delta = envelope.begin()->distanceTo(pt); insertPoint = envelope.insert(pt).first; } else { PointMap::iterator leftNeighbour(rightNeighbour); leftNeighbour--; if(Above(pt, *leftNeighbour, *rightNeighbour)) { // aha, bod nepatří dovnitř, takže zvětšíme obal delta = leftNeighbour->distanceTo(pt) + pt.distanceTo(*rightNeighbour) - leftNeighbour->distanceTo(*rightNeighbour); insertPoint = envelope.insert(pt).first; } } if(insertPoint != envelope.end()) { // Kontrola obálky směrem vlevo if(insertPoint != envelope.begin()) { PointMap::iterator prev = insertPoint; prev--; while(prev != envelope.begin()) { PointMap::iterator pprev = prev; pprev--; // body jsou za sebou v tomto pořadí: pprev -> prev -> insertPoint if(!Above(*prev, *pprev, *insertPoint)) { delta -= pprev->distanceTo(*prev) + prev->distanceTo(*insertPoint) - pprev->distanceTo(*insertPoint); envelope.erase(prev); insertPoint = envelope.find(pt); prev = insertPoint; prev--; // tj. vlastně pprev se stane předchůdcem insertPointu } else break; // dál už je to v pořádku } } if(insertPoint != --envelope.end()) { PointMap::iterator next = insertPoint; next++; while(next != --envelope.end()) { PointMap::iterator nnext = next; nnext++; // body jsou za sebou v tomto pořadí: insertPoint -> next -> nnext if(!Above(*next, *insertPoint, *nnext)) { delta -= insertPoint->distanceTo(*next) + next->distanceTo(*nnext) - insertPoint->distanceTo(*nnext); envelope.erase(next); insertPoint = envelope.find(pt); next = insertPoint; next++; // tj. vlastně nnext se stane následníkem insertPointu } else break; // dál už je to v pořádku } } } return delta; } double EndsDistance(PointMap& upper, PointMap& lower) { PointMap::iterator lowerEnd = lower.end(), upperEnd = upper.end(); lowerEnd--; upperEnd--; return upper.begin()->distanceTo(lower.begin()->flip()) + upperEnd->distanceTo(lowerEnd->flip()); } int main() { int m, n; PointMap upper, lower; // upravovatelná horní a dolní obálka množiny bodu scanf("%d\n", &n); Point pt = scanpt(); upper.insert(pt); lower.insert(pt.flip()); double sum = 0, delta = 0; for(int i = 1; i < n; i++) { pt = scanpt(); delta = -EndsDistance(upper, lower); delta += AddPoint(upper, pt); delta += AddPoint(lower, pt.flip()); // body delta += EndsDistance(upper, lower); sum += delta; } printf("%.5f\n", sum); scanf("%d", &m); for(int i = 0; i < m; i++) { pt = scanpt(); delta = -EndsDistance(upper, lower); delta += AddPoint(upper, pt); delta += AddPoint(lower, pt.flip()); delta += EndsDistance(upper, lower); printf("%.5f\n", delta); } return 0; }