Ada Lovelace National Girls' Programming Contest 2021

expansion.cc

#include <bits/stdc++.h>

using namespace std;

typedef double Tf;
typedef Tf Ti;	// int/ll for exactness

const Tf EPS = 1e-7;
const Tf INF = 1e20;

// compares two floating values x and y 
inline int dcmp(Tf x, Tf y = 0) {
	return fabs(x - y) < EPS ? 0 : (x < y ? -1 : 1);
}

typedef struct Pt {
	Ti x, y;
	Pt(Ti x = 0, Ti y = 0) : x(x), y(y) { }

	bool operator == (const Pt& p) const { return !dcmp(x, p.x) and !dcmp(y, p.y); }
	bool operator != (const Pt& p) const { return !(*this == p); }
	bool operator < (const Pt& p) const { return dcmp(x, p.x) < 0 or (!dcmp(x, p.x) and dcmp(y, p.y) < 0); }
	bool operator > (const Pt& p) const { return p < *this; }

	Pt operator + (const Pt& p) const { return Pt(x + p.x, y + p.y); }
	Pt operator - (const Pt& p) const { return Pt(x - p.x, y - p.y); }
	Pt operator * (const auto v) const { return Pt(x * v, y * v); }
	Pt operator / (const auto v) const { return Pt(x / v, y / v); }

	friend istream& operator >> (istream& is, Pt& p) { return is >> p.x >> p.y; }
	friend ostream& operator << (ostream& os, const Pt& p) { return os << "(" << p.x << ", " << p.y << ")"; }
} Vec;

Tf angle_with_xaxis(Vec a) {
	return atan2(a.y, a.x);
}

Vec rotate(Vec a, Tf ang) {
	return Vec(a.x * cos(ang) - a.y * sin(ang), a.x * sin(ang) + a.y * cos(ang));
}

typedef struct Seg {
	Pt a, b;
	Seg() { }
	Seg(Pt p, Pt q) : a(p), b(q) { }
} Line;

typedef vector<Pt> Poly;

void good_ones(vector<Poly>& poly, Tf xm) {
	vector<Poly> ret;
	for(Poly& p : poly) {
		bool all_left = true, all_right = true;
		for(Pt pt : p) {
			if(dcmp(pt.x, 0) > 0) all_left = false;
			if(dcmp(pt.x, xm) < 0) all_right = false;
		}
		if(all_left or all_right) continue;
		ret.push_back(p);
	}
	poly = ret;
}

Tf solve(Seg& pq, vector<Poly>& poly) {
	// horizontally align everything
	pq.b = pq.b - pq.a;
	for(Poly& p : poly) {
		for(Pt& pt : p) pt = pt - pq.a;
	}
	pq.a = pq.a - pq.a;
	Tf ang = -angle_with_xaxis(pq.b);
	pq.b = rotate(pq.b, ang);
	for(Poly& p : poly) {
		for(Pt& pt : p) pt = rotate(pt, ang);
	}

	// asserts
	assert(dcmp(pq.b.y) == 0);
	assert(dcmp(pq.b.x) > 0);
	assert(dcmp(pq.a.x) == 0 and dcmp(pq.a.y) == 0);

	// remove unnecessary polygons
	good_ones(poly, pq.b.x);

	Tf up = INF, dn = INF;

	// points in the range
	for(Poly& p : poly) {
		for(Pt& pt : p) {
			if(dcmp(pt.x, pq.a.x) >= 0 and dcmp(pt.x, pq.b.x) <= 0) {
				assert(dcmp(pt.y));		// point must not be on the line segment
				if(pt.y > 0) up = min(up, pt.y);
				else dn = min(dn, fabs(pt.y));
			}
		}
	}

	// intersecting segments
	for(Poly& p : poly) {
		int n = p.size();
		for(int i=0; i<n; ++i) {
			int j = (i + 1) % n;
			if(dcmp(p[i].x, p[j].x) == 0) continue;
			if(dcmp(p[i].x, pq.a.x) * dcmp(p[j].x, pq.a.x) < 0) {
				Tf y = p[i].y + (pq.a.x - p[i].x) / (p[j].x - p[i].x) * (p[j].y - p[i].y);
				assert(dcmp(y));	// point must not be on the line segment
				if(y > 0) up = min(up, y);
				else dn = min(dn, fabs(y));
			}
			if(dcmp(p[i].x, pq.b.x) * dcmp(p[j].x, pq.b.x) < 0) {
				Tf y = p[i].y + (pq.b.x - p[i].x) / (p[j].x - p[i].x) * (p[j].y - p[i].y);
				assert(dcmp(y));	// point must not be on the line segment
				if(y > 0) up = min(up, y);
				else dn = min(dn, fabs(y));
			}
		}
	}
	
	return up + dn;
}

int main() {
	// ios::sync_with_stdio(false);
	// cin.tie(0);

	int t;
	assert(cin >> t);
	assert(t >= 1 and t <= 100);

	while(t--) {
		Seg pq;
		assert(cin >> pq.a >> pq.b);

		int n;
		assert(cin >> n);
		assert(n >= 2 and n <= 100);

		vector<Poly> poly(n);
		for(Poly& p : poly) {
			int k;
			assert(cin >> k);
			assert(k >= 3 and k <= 10);
			p.resize(k);
			for(Pt& pt : p) assert(cin >> pt);
		}

		Tf res = solve(pq, poly);
		cout << fixed << setprecision(10) << res << "\n";
	}

	string temp;
	assert(!(cin >> temp));

	return 0;
}