Submission #305617

#	Time	Username	Problem	Language	Result	Execution time	Memory
305617		youngyojun	Fences (JOI18_fences)	C++17	100 / 100	907 ms	1272 KiB

fences

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;
const ld EPS = ld(1e-8)/2;
bool isZero(ld n) { return abs(n) < EPS; }
bool isSame(ld a, ld b) { return isZero(a-b); }
ld pw(ld n) { return n*n; }
ld size(pdd a) { return sqrt(pw(a.first) + pw(a.second)); }
int sign(ld n) { return isZero(n) ? 0 : (0 < n ? 1 : -1); }
 
struct Vec {
	Vec(ld x = 0, ld y = 0, ld z = 0) : x(x), y(y), z(z) {}
	ld x, y, z;
 
	bool operator == (const Vec& t) const {
		return isZero(x - t.x) && isZero(y - t.y) && isZero(z - t.z);
	}
	Vec operator + (const Vec& t) const { return Vec(x+t.x, y+t.y, z+t.z); }
	Vec operator - (const Vec& t) const { return Vec(x-t.x, y-t.y, z-t.z); }
	Vec operator * (const ld& t) const { return Vec(x*t, y*t, z*t); }
	Vec operator / (const ld& t) const { return Vec(x/t, y/t, z/t); }
	Vec operator * (const Vec& t) const { return Vec(y*t.z - z*t.y, z*t.x - x*t.z, x*t.y - y*t.x); }
	ld operator / (const Vec& t) const { return x*t.x + y*t.y + z*t.z; }
	ld len() const { return sqrt(x*x + y*y + z*z); }
	ld pwlen() const { return x*x + y*y + z*z; }
	void norm() {
		const ld L = len();
		if(!isZero(L)) *this = *this / L;
	}
};
typedef vector<Vec> Cec;
ld ccw(const Vec& a, const Vec& b, const Vec& c) { return ((b-a) * (c-a)).len(); }
// a -- b -- c : True, Otherwise : False
bool isbet(Vec a, Vec b, Vec c) {
	if(a == b || b == c) return true;
 
	ld x = (b-a).pwlen(), y = (c-b).pwlen(), z = (c-a).pwlen();
	if(!isZero(x*y*4 - pw(x+y-z))) return false;
 
	if(a.x < c.x && (b.x < a.x-EPS || c.x+EPS < b.x)) return false;
	if(a.x > c.x && (b.x < c.x-EPS || a.x+EPS < b.x)) return false;
	if(a.y < c.y && (b.y < a.y-EPS || c.y+EPS < b.y)) return false;
	if(a.y > c.y && (b.y < c.y-EPS || a.y+EPS < b.y)) return false;
	return true;
}
bool isco(Vec a, Vec b, Vec c) { return isZero(ccw(a, b, c)); }
pair<Vec, bool> intersect(Vec a, Vec b, Vec c, Vec d) {
	Vec u = b-a, v = d-c, z = c-a, vz = v*z, vu = v*u;
	if(isZero(vu.len())) return {Vec(), false};
	return {a + u * (vz.len() / vu.len() * sign(vz / vu)), true};
}
Vec project(Vec a, Vec b, Vec c) { b.norm(); return b * ((c-a) / b) + a; }
 
const int MAXN = 205;
 
double D[MAXN*2][MAXN*2];
 
Vec A[MAXN], B[MAXN];
int SPI[MAXN];
 
const int CPV[28][5] = {
	{1, 0}, {1, 1}, {1, 2}, {1, 3},
	{2, 0, 1}, {2, 1, 2}, {2, 2, 3}, {2, 3, 0},
	{2, 1, 0}, {2, 2, 1}, {2, 3, 2}, {2, 0, 3},
	{3, 0, 1, 2}, {3, 1, 2, 3}, {3, 2, 3, 0}, {3, 3, 0, 1},
	{3, 2, 1, 0}, {3, 3, 2, 1}, {3, 0, 3, 2}, {3, 1, 0, 3},
	{4, 0, 1, 2, 3}, {4, 1, 2, 3, 0}, {4, 2, 3, 0, 1}, {4, 3, 0, 1, 2},
	{4, 3, 2, 1, 0}, {4, 2, 1, 0, 3}, {4, 1, 0, 3, 2}, {4, 0, 3, 2, 1}
};
Vec BP[4], CP[4];
Vec lv;
 
double Ans;
int N, C;
 
bool isp(Vec a, Vec b) {
	if(a == b) return true;
	Vec ret; bool chk;
	for(int i = 0; i < 4; i++) {
		tie(ret, chk) = intersect(a, b, BP[i], BP[(i+1)%4]);
		if(chk && isbet(BP[i], ret, BP[(i+1)%4]) && isbet(a, ret, b))
			return false;
	}
	return true;
}
bool ispl(Vec a, Vec b) {
	if(a == b) return false;
	Vec ret; bool chk;
	tie(ret, chk) = intersect(a, b, Vec(), lv);
	return chk && EPS < ret.x && EPS < ret.y && isbet(a, ret, b);
}
 
 
void upd(Cec V, ld &reta, ld &retb) {
	ld ret = 0;
	bool flag = false;
 
	for(int i = 1, n = sz(V); i < n; i++) {
		if(!isp(V[i-1], V[i])) return;
		flag ^= ispl(V[i-1], V[i]);
		ret += (V[i] - V[i-1]).len();
	}
 
	if(flag) upmin(retb, ret);
	else upmin(reta, ret);
}
void upd1(Vec a, Vec b, Vec c, ld &reta, ld &retb) {
	Vec p = project(b, c-b, a);
	if(!isbet(b, p, c)) return;
	upd(Cec{a, p}, reta, retb);
}
void f(Vec ps, Vec pe, Vec qs, Vec qe, ld &reta, ld &retb, bool iss) {
	reta = retb = INFLL;
 
	if(!iss) {
		upd(Cec{ps, qs}, reta, retb);
		upd(Cec{ps, qe}, reta, retb);
		upd(Cec{pe, qs}, reta, retb);
		upd(Cec{pe, qe}, reta, retb);
 
		upd1(ps, qs, qe, reta, retb);
		upd1(pe, qs, qe, reta, retb);
		upd1(qs, ps, pe, reta, retb);
		upd1(qe, ps, pe, reta, retb);
	}
 
	for(int cpvi = 0, cpvsz; cpvi < 28; cpvi++) {
		cpvsz = CPV[cpvi][0];
		if(iss && cpvsz < 3) continue;
 
		Cec PV, QV;
		PV.eb(ps); PV.eb(pe); QV.eb(qs); QV.eb(qe);
 
		{
			Vec p = project(ps, pe-ps, CP[CPV[cpvi][1]]);
			if(isbet(ps, p, pe)) PV.eb(p);
		}
		{
			Vec p = project(qs, qe-qs, CP[CPV[cpvi][cpvsz]]);
			if(isbet(qs, p, qe)) QV.eb(p);
		}
 
		Vec ph, qh;
 
		{
			ld pl = INFLL;
			for(auto &p : PV) {
				ld t = (p - CP[CPV[cpvi][1]]).len();
				if(pl <= t) continue;
				ph = p; pl = t;
			}
		}
		{
			ld ql = INFLL;
			for(auto &p : QV) {
				ld t = (p - CP[CPV[cpvi][cpvsz]]).len();
				if(ql <= t) continue;
				qh = p; ql = t;
			}
		}
 
		Cec Path;
		Path.eb(ph);
		for(int i = 1; i <= cpvsz; i++)
			Path.eb(CP[CPV[cpvi][i]]);
		Path.eb(qh);
		upd(Path, reta, retb);
	}
}
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	srand(20010610);
	lv.x = ld(rand() % 708790 + 337) / ld(rand() % 900 + 755);
	lv.y = ld(rand() % 632048 + 469) / ld(rand() % 908 + 147);
 
	cin >> N >> C;
	for(int i = 1; i <= N; i++)
		cin >> A[i].x >> A[i].y >> B[i].x >> B[i].y;
 
	{
		ld CEPS = ld(1e-5);
		BP[0] = Vec(ld(C) - CEPS, ld(C) - CEPS);
		BP[1] = Vec(ld(C) - CEPS, ld(-C) + CEPS);
		BP[2] = Vec(ld(-C) + CEPS, ld(-C) + CEPS);
		BP[3] = Vec(ld(-C) + CEPS, ld(C) - CEPS);
 
		CP[0] = Vec(C, C);
		CP[1] = Vec(C, -C);
		CP[2] = Vec(-C, -C);
		CP[3] = Vec(-C, C);
	}
 
	{
		ld CEPS = ld(1e-4)/2;
		for(int i = N; i; i--) {
			Vec a = A[i], b = B[i];
			if(!ispl(a, b)) continue;
 
			Vec p = intersect(a, b, Vec(), lv).first;
			Vec v = p-a; v.norm(); v = v * CEPS;
 
			N++; A[N] = a; B[N] = p-v;
			A[i] = p+v; B[i] = b;
 
			SPI[i] = N;
		}
	}
 
	for(int i = 1; i <= N; i++) for(int j = i; j <= N; j++) {
		ld a, b; f(A[i], B[i], A[j], B[j], a, b, i == j);
		D[i*2][j*2] = D[i*2-1][j*2-1] = D[j*2][i*2] = D[j*2-1][i*2-1] = a;
		D[i*2-1][j*2] = D[i*2][j*2-1] = D[j*2-1][i*2] = D[j*2][i*2-1] = b;
	}
 
	for(int i = 1; i <= N; i++) {
		D[i*2][i*2] = D[i*2-1][i*2-1] = 0;
 
		int t = SPI[i];
		if(t) D[i*2][t*2-1] = D[i*2-1][t*2] = D[t*2][i*2-1] = D[t*2-1][i*2] = 0;
	}
 
	for(int k = 1; k <= N*2; k++) for(int i = 1; i <= N*2; i++) for(int j = 1; j <= N*2; j++)
		upmin(D[i][j], D[i][k] + D[k][j]);
	
	Ans = ld(C) * 8;
	for(int i = 1; i <= N; i++) upmin(Ans, D[i*2][i*2-1]);
 
	printf("%.10lf\n", Ans);
	return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 33 / 33
• Subtask 3: 49 / 49