Submission #428797

# Submission time Handle Problem Language Result Execution time Memory
428797 2021-06-15T14:34:21 Z youngyojun 색종이 (kriii3_T) C++17
109 / 109
865 ms 1484 KB
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) (V).begin(),(V).end()
#define fi first
#define se second
using namespace std;
typedef long double ld;
typedef pair<ld, ld> pdd;
const ld PI = acos(0)*2;
const ld eps = 1e-10;
bool isZero(const ld &x) { return -eps <= x && x <= eps; }
bool isSame(const ld &a, const ld &b) { return isZero(a-b); }
bool isBet(const ld &a, const ld &b, const ld &c) {
	return a-eps <= b && b-eps <= c
		|| c-eps <= b && b-eps <= a;
}
bool isBet(const pdd &a, const pdd &b, const pdd &c) {
	return isBet(a.fi, b.fi, c.fi)
		&& isBet(a.se, b.se, c.se);
}
ld norm(ld theta) {
	theta = fmod(theta, PI*2);
	while(theta < 0) theta += PI*2;
	return theta;
}
bool operator == (const pdd &a, const pdd &b) { return isSame(a.fi, b.fi) && isSame(a.se, b.se); }
bool operator != (const pdd &a, const pdd &b) { return !(a == b); }
pdd operator + (const pdd &a, const pdd &b) { return pdd(a.fi + b.fi, a.se + b.se); }
pdd operator - (const pdd &a, const pdd &b) { return pdd(a.fi - b.fi, a.se - b.se); }
pdd operator * (const pdd &a, const ld &b) { return pdd(a.fi * b, a.se * b); }
pdd operator / (const pdd &a, const ld &b) { return pdd(a.fi / b, a.se / b); }
ld operator * (const pdd &a, const pdd &b) { return a.fi * b.se - a.se * b.fi; }
ld operator / (const pdd &a, const pdd &b) { return a.fi * b.fi + a.se * b.se; }
ld dist2(const pdd &v) { return v/v; }
pdd rotNVec(const ld &theta) { return pdd(cos(theta), sin(theta)); }
ld ccw(const pdd &a, const pdd &b, const pdd &c) { return a*b + b*c + c*a; }
bool isSameDir(const pdd &a, const pdd &b, const pdd &c, const pdd &d) {
	return sqrt(dist2(b-a)) + sqrt(dist2(d-c)) < sqrt(dist2(d-a));
}

pdd readPdd() {
	pdd p;
	cin >> p.fi >> p.se;
	return p;
}

struct LINE {
	LINE(int idx, pdd s, pdd e)
		: idx(idx), s(s), e(e) {}
	int idx;
	pdd s, e;
};

struct TRI {
	int idx;

	pdd p[3];

	void input() {
		for(int i = 3; i--;)
			p[i] = readPdd();
		if(ccw(p[0], p[1], p[2]) <= 0)
			swap(p[1], p[2]);
	}
};

struct CIR {
	int idx;

	pdd p;
	ld r;

	void input() {
		p = readPdd();
		cin >> r;
	}
};

bool isSame(const CIR &a, const CIR &b) {
	return a.p == b.p && isSame(a.r, b.r);
}

bool isIn(const CIR &a, const pdd &p) {
	return dist2(p - a.p) <= a.r*a.r - eps;
}

bool isIn(const TRI &a, const pdd &p) {
	return eps <= ccw(a.p[0], a.p[1], p)
		&& eps <= ccw(a.p[1], a.p[2], p)
		&& eps <= ccw(a.p[2], a.p[0], p);
}

bool onTri(const TRI &a, const pdd &p, const pdd &s, const pdd &e) {
	return isBet(a.p[0], p, a.p[1]) && isZero(ccw(a.p[0], a.p[1], p)) && isSameDir(a.p[0], s, e, a.p[1])
		|| isBet(a.p[1], p, a.p[2]) && isZero(ccw(a.p[1], a.p[2], p)) && isSameDir(a.p[1], s, e, a.p[2])
		|| isBet(a.p[2], p, a.p[0]) && isZero(ccw(a.p[2], a.p[0], p)) && isSameDir(a.p[2], s, e, a.p[0]);
}

ld integral(const CIR &cir, const ld &s, const ld &e) {
	return cir.p.fi * cir.r * (sin(e) - sin(s))
		+ cir.r * cir.r * (e-s + (sin(e+e) - sin(s+s)) / 2) / 2;
}

ld integral(const pdd &s, const pdd &e) {
	return (e.se - s.se) * (s.fi + e.fi) / 2;
}

bool cirInsec(const pdd &p, const ld &r, const ld &R, ld &th1, ld &th2) {
	ld d2 = p/p, d = sqrt(d2);
	ld cosGamma = (r*r + d2 - R*R) / (r*d*2);
	if(cosGamma < -1 || 1 < cosGamma)
		return false;
	
	ld gamma = acos(cosGamma);
	ld phi = atan2(p.se, p.fi);

	th1 = norm(PI + phi - gamma);
	th2 = norm(PI + phi + gamma);
	if(th1 > th2) swap(th1, th2);
	return true;
}

int cirLineInsec(const pdd &p, const ld &r, const pdd &a, const pdd &b
				, ld &th1, ld &th2, pdd &sec1, pdd &sec2) {
	pdd v = b-a, n(v.se, -v.fi);
	ld d = (p-a) / n, nsz = sqrt(n/n);
	if(d < 0) {
		d = -d;
		n = pdd(-n.fi, -n.se);
	}
	d /= nsz;

	ld cosGamma = d / r;
	if(cosGamma < 0 || 1 < cosGamma)
		return 0;
	
	ld gamma = acos(cosGamma);
	ld phi = atan2(n.se, n.fi);

	th1 = norm(PI + phi - gamma);
	th2 = norm(PI + phi + gamma);
	if(th1 > th2) swap(th1, th2);

	sec1 = p + rotNVec(th1) * r;
	sec2 = p + rotNVec(th2) * r;

	bool flag1 = isBet(a, sec1, b);
	bool flag2 = isBet(a, sec2, b);

	if(flag1)
		return flag2 ? 2 : 1;
	
	if(!flag2)
		return 0;
	
	swap(th1, th2);
	swap(sec1, sec2);
	return 1;
}

int lineInsec(const pdd &a, const pdd &b, const pdd &c, const pdd &d, pdd &sec1, pdd &sec2) {
	pdd v = b-a, u = d-c;
	if(isZero(u*v)) {
		if(!isZero(ccw(a, b, c)))
			return 0;

		sec1 = c; sec2 = d;
		bool flag1 = isBet(a, c, b);
		bool flag2 = isBet(a, d, b);

		if(flag1)
			return flag2 ? 2 : 1;

		if(!flag2)
			return 0;

		swap(sec1, sec2);
		return 1;
	}

	pdd n(v.se, -v.fi);
	ld r = ((a-c)/n) / (u/n);

	sec1 = c + u * r;

	return isBet(a, sec1, b) && isBet(c, sec1, d) && isZero(ccw(a, b, sec1)) ? 1 : 0;
}

vector<TRI> TV;
vector<LINE> LV;
vector<CIR> CV;

ld Ans[205][205];

int N;

void solveCir() {
	for(const CIR &cir : CV) {
		const int idx = cir.idx;

		vector<ld> V = {0, PI*2};

		for(const CIR &o : CV) if(!isSame(cir, o)) {
			ld th1, th2;
			if(cirInsec(cir.p - o.p, cir.r, o.r, th1, th2)) {
				V.eb(th1);
				V.eb(th2);
			}
		}

		for(const LINE &o : LV) {
			ld th[2]; pdd sec[2];
			int ret = cirLineInsec(cir.p, cir.r, o.s, o.e, th[0], th[1], sec[0], sec[1]);
			while(ret--) V.eb(th[ret]);
		}

		sort(allv(V));
		V.erase(unique(allv(V), [&](const ld &a, const ld &b) {
			return isSame(a, b);
		}), V.end());

		int n = sz(V);
		for(int i = 1; i < n; i++) {
			ld ths = V[i-1], the = V[i];
			ld val = integral(cir, ths, the);
			pdd cp = cir.p + rotNVec((ths + the) / 2) * cir.r;

			int si = 0, ei = N+1;

			for(const CIR &o : CV) {
				if(si < o.idx && o.idx < idx && !isSame(cir, o) && isIn(o, cp))
					si = o.idx;
				if(idx < o.idx && o.idx < ei && (isSame(cir, o) || isIn(o, cp)))
					ei = o.idx;
			}

			for(const TRI &o : TV) {
				if(si < o.idx && o.idx < idx && isIn(o, cp))
					si = o.idx;
				if(idx < o.idx && o.idx < ei && isIn(o, cp))
					ei = o.idx;
			}

			for(int i = idx; i < ei; i++) {
				Ans[i][idx] += val;
				Ans[i][si] -= val;
			}
		}
	}
}

void solveLine() {
	for(const LINE &line : LV) {
		const int idx = line.idx;

		vector<pdd> V = {line.s, line.e};

		for(const CIR &o : CV) {
			ld th[2]; pdd sec[2];
			int ret = cirLineInsec(o.p, o.r, line.s, line.e, th[0], th[1], sec[0], sec[1]);
			while(ret--) V.eb(sec[ret]);
		}

		for(const LINE &o : LV) {
			pdd sec[2];
			int ret = lineInsec(line.s, line.e, o.s, o.e, sec[0], sec[1]);
			while(ret--) V.eb(sec[ret]);
		}

		{
			const pdd v = line.e - line.s;
			for(auto &v : V) v = v - line.s;
			const pdd n(-v.se, v.fi);
			for(auto &v : V) v = v - (n * ((v/n) / sqrt(n/n)));
			sort(allv(V), [&](const pdd &a, const pdd &b) {
				return a/v < b/v;
			});
			V.erase(unique(allv(V), [&](const pdd &a, const pdd &b) {
				return a == b;
			}), V.end());
			for(auto &v : V) v = v + line.s;
		}

		int n = sz(V);
		for(int i = 1; i < n; i++) {
			pdd s = V[i-1], e = V[i], cp = (s+e) * 0.5;
			ld val = integral(s, e);

			int si = 0, ei = N+1;

			for(const CIR &o : CV) {
				if(si < o.idx && o.idx < idx && isIn(o, cp))
					si = o.idx;
				if(idx < o.idx && o.idx < ei && isIn(o, cp))
					ei = o.idx;
			}

			for(const TRI &o : TV) {
				if(si < o.idx && o.idx < idx && !onTri(o, cp, s, e) && isIn(o, cp))
					si = o.idx;
				if(idx < o.idx && o.idx < ei && (onTri(o, cp, s, e) || isIn(o, cp)))
					ei = o.idx;
			}

			for(int i = idx; i < ei; i++) {
				Ans[i][idx] += val;
				Ans[i][si] -= val;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N;
	for(int i = 1; i <= N; i++) {
		int t; cin >> t;
		if(1 == t) {
			TV.eb();
			auto &t = TV.back();
			t.idx = i;
			t.input();

			LV.eb(i, t.p[0], t.p[1]);
			LV.eb(i, t.p[1], t.p[2]);
			LV.eb(i, t.p[2], t.p[0]);
		} else {
			CV.eb();
			CV.back().idx = i;
			CV.back().input();
		}
	}

	solveCir();
	solveLine();

	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= i; j++)
			printf("%.15Lf ", Ans[i][j]);
		putchar('\n');
	}
	return 0;
}

Compilation message

paper.cpp: In function 'bool isBet(const ld&, const ld&, const ld&)':
paper.cpp:15:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   15 |  return a-eps <= b && b-eps <= c
      |         ~~~~~~~~~~~^~~~~~~~~~~~~
paper.cpp: In function 'bool onTri(const TRI&, const pdd&, const pdd&, const pdd&)':
paper.cpp:95:68: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   95 |  return isBet(a.p[0], p, a.p[1]) && isZero(ccw(a.p[0], a.p[1], p)) && isSameDir(a.p[0], s, e, a.p[1])
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
paper.cpp:97:65: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   97 |   || isBet(a.p[2], p, a.p[0]) && isZero(ccw(a.p[2], a.p[0], p)) && isSameDir(a.p[2], s, e, a.p[0]);
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 135 ms 1256 KB Output is correct
2 Correct 128 ms 1248 KB Output is correct
3 Correct 137 ms 1276 KB Output is correct
4 Correct 121 ms 1244 KB Output is correct
5 Correct 123 ms 1260 KB Output is correct
6 Correct 127 ms 1252 KB Output is correct
7 Correct 144 ms 1348 KB Output is correct
8 Correct 118 ms 1256 KB Output is correct
9 Correct 105 ms 1260 KB Output is correct
10 Correct 133 ms 1244 KB Output is correct
11 Correct 43 ms 1252 KB Output is correct
12 Correct 62 ms 1248 KB Output is correct
13 Correct 92 ms 1252 KB Output is correct
14 Correct 89 ms 1348 KB Output is correct
15 Correct 92 ms 1248 KB Output is correct
16 Correct 76 ms 1252 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 180 ms 1352 KB Output is correct
2 Correct 191 ms 1308 KB Output is correct
3 Correct 179 ms 1408 KB Output is correct
4 Correct 189 ms 1348 KB Output is correct
5 Correct 178 ms 1348 KB Output is correct
6 Correct 865 ms 1372 KB Output is correct
7 Correct 154 ms 1348 KB Output is correct
8 Correct 244 ms 1328 KB Output is correct
9 Correct 191 ms 1348 KB Output is correct
10 Correct 189 ms 1308 KB Output is correct
11 Correct 386 ms 1476 KB Output is correct
12 Correct 445 ms 1368 KB Output is correct
13 Correct 78 ms 1484 KB Output is correct
14 Correct 60 ms 1380 KB Output is correct
15 Correct 88 ms 1280 KB Output is correct
16 Correct 162 ms 1396 KB Output is correct
17 Correct 152 ms 1316 KB Output is correct
18 Correct 153 ms 1352 KB Output is correct
19 Correct 145 ms 1436 KB Output is correct
20 Correct 140 ms 1368 KB Output is correct