| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 998801 |
2024-06-14T17:02:12 Z |
crimson231 |
색종이 (kriii3_T) |
C++17 |
|
71 ms |
1496 KB |
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <vector>
typedef long long ll;
//typedef double ld;
typedef long double ld;
typedef std::vector<ld> vld;
const ld INF = 1e17;
const ld TOL = 1e-13;
const ld PI = acosl(-1);
const int LEN = 205;
inline bool zero(const ld& x) { return -TOL <= x && x <= TOL; }
inline ll sq(int x) { return (ll)x * x; }
inline ld norm(ld th) {
while (th < 0) th += 2 * PI;
while (th >= 2 * PI) th -= 2 * PI;
return th;
}
enum Geo {
TRI,
CIR,
};
int N;
ld A[LEN][LEN];
struct Pos {
ld x, y;
Pos(ld x = 0, ld y = 0) : x(x), y(y) {}
bool operator == (const Pos& p) const { return zero(x - p.x) && zero(y - p.y); }
bool operator != (const Pos& p) const { return !zero(x - p.x) || !zero(y - p.y); }
Pos operator + (const Pos& p) const { return { x + p.x, y + p.y }; }
Pos operator - (const Pos& p) const { return { x - p.x, y - p.y }; }
Pos operator * (const ld& s) const { return { x * s, y * s }; }
ld operator * (const Pos& p) const { return x * p.x + y * p.y; }
ld operator / (const Pos& p) const { return x * p.y - y * p.x; }
Pos operator - () const { return { -x, -y }; }
Pos operator ~ () const { return { y, -x }; }
Pos rot(ld the) const { return Pos(x * cosl(the) - y * sinl(the), x * sinl(the) + y * cosl(the)); }
ld Euc() const { return x * x + y * y; }
//ld mag() const { return hypotl(x, y); }
ld mag() const { return sqrt(Euc()); }
ld rad() const { return norm(atan2(y, x)); }
friend std::istream& operator >> (std::istream& is, Pos& p) { is >> p.x >> p.y; return is; }
friend std::ostream& operator << (std::ostream& os, const Pos& p) { os << p.x << " " << p.y; return os; }
};
typedef std::vector<Pos> Polygon;
struct Seg {
Pos s, e;
Seg(Pos S = Pos(), Pos E = Pos()) : s(S), e(E) {}
ld green(const ld& v) const { return s / e * v * .5; }
};
struct Triangle {
Pos a, b, c;
Triangle(Pos p = Pos(), Pos q = Pos(), Pos r = Pos()) {
if ((q - p) / (r - q) > 0) std::swap(q, r);
a = p; b = q; c = r;
}
int inner_check(const Pos& p, const Pos& v) const {
ld f1 = (b - a) / (p - a);
ld f2 = (c - b) / (p - b);
ld f3 = (a - c) / (p - c);
//if (sign(f1) < 0 || sign(f2) < 0 || sign(f3) < 0) return 0;
//if (f1 < -TOL || f2 < -TOL || f3 < -TOL) return 0;
if (f1 > TOL || f2 > TOL || f3 > TOL) return 0;
if (zero(f1)) return v / (b - a) > 0 ? 2 : 0;//on_seg && centripetal
if (zero(f2)) return v / (c - b) > 0 ? 2 : 0;
if (zero(f3)) return v / (a - c) > 0 ? 2 : 0;
return 1;
}
};
struct Circle {
Pos c;
int r;
Circle(Pos C = Pos(0, 0), int R = 0) : c(C), r(R) {}
bool operator == (const Circle& C) const { return c == C.c && r == C.r; }
bool operator >= (const Pos& p) const { return r * r >= (c - p).Euc(); }
ld area(const ld& lo, const ld& hi) const { return (hi - lo) * r * r; }
ld rad(Pos p) const {
ld v = atan2(p.y - c.y, p.x - c.x);
if (v < 0) v += 2 * PI;
return v;
}
ld green(const ld& lo, const ld& hi) const {
ld v1 = r * r * (ld).5 * ((hi - lo) - (ld).5 * (sin(hi * 2) - sin(lo * 2)));
v1 -= r * c.y * (cos(hi) - cos(lo));
return v1;
}
friend std::ostream& operator << (std::ostream& os, const Circle& c) { os << c.c << " " << c.r; return os; }
};
struct Shape {
Geo type;
Triangle T;
Circle C;
Shape(int t = 0, int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0) {
type = (Geo)t;
if (type == TRI) T = Triangle(Pos(a, b), Pos(c, d), Pos(e, f));
else if (type == CIR) C = Circle(Pos(a, b), c);
}
} C[LEN];
ld intersection(const Seg& s1, const Seg& s2) {
const Pos& p1 = s1.s, p2 = s1.e, q1 = s2.s, q2 = s2.e;
ld det = (q2 - q1) / (p2 - p1);
if (zero(det)) return -1;
ld a1 = ((q2 - q1) / (q1 - p1)) / det;
ld a2 = ((p2 - p1) / (p1 - q1)) / -det;
//if (sign(a1) >= 0 && sign(1 - a1) >= 0 && sign(a2) >= 0 && sign(1 - a1) >= 0) return a1;
if (0 <= a1 && a1 <= 1 && -TOL <= a2 && a2 <= 1 + TOL) return a1;
return -1;
}
vld circle_line_intersections(const Pos& s, const Pos& e, const Circle& q, const bool& f = 0) {
Pos vec = e - s;
Pos OM = s - q.c;
ld a = vec.Euc();
ld b = vec * OM;
ld c = OM.Euc() - q.r * q.r;
ld J = b * b - a * c;
if (J < -TOL) return {};
ld det = sqrt(std::max((ld)0, J));
ld lo = (-b - det) / a;
ld hi = (-b + det) / a;
vld ret;
if (f) {
if (0 <= hi && hi <= 1) ret.push_back(hi);
if (zero(det)) return ret;
if (0 <= lo && lo <= 1) ret.push_back(lo);
}
else {
auto the = [&](ld rt) { return q.rad(s + (e - s) * rt); };
if (-TOL <= hi && hi <= 1 + TOL) ret.push_back(the(hi));
if (zero(det)) return ret;
if (-TOL <= lo && lo <= 1 + TOL) ret.push_back(the(lo));
}
return ret;
}
vld intersection(const Circle& a, const Circle& b) {
Pos ca = a.c, cb = b.c;
Pos vec = cb - ca;
ll ra = a.r, rb = b.r;
ld distance = vec.mag();
ld rd = vec.rad();
if (vec.Euc() > sq(ra + rb) + TOL) return {};
if (vec.Euc() < sq(ra - rb) - TOL) return {};
ld X = (ra * ra - rb * rb + vec.Euc()) / (2 * distance * ra);
if (X < -1) X = -1;
if (X > 1) X = 1;
ld h = acos(X);
vld ret = {};
ret.push_back(norm(rd + h));
if (zero(h)) return ret;
ret.push_back(norm(rd - h));
return ret;
}
void green_seg(const Seg& S, const int& I) {//refer to cki86201
//if (zero(S.s / S.e)) return;
if (S.s.x == S.e.x) return;
vld VA = { 0, 1 };
const Pos& a = S.s, b = S.e;
for (int j = 1; j <= N; j++) {
if (I == j) continue;
if (C[j].type == TRI) {
Pos* tri[] = { &C[j].T.a, &C[j].T.b, &C[j].T.c };
for (int k = 0; k < 3; k++) {
const Pos& q1 = *tri[k], & q2 = *tri[(k + 1) % 3];
ld r = intersection(S, Seg(q1, q2));
if (r > -.5) VA.push_back(r);
}
}
if (C[j].type == CIR) {
Circle& c = C[j].C;
vld inx;
inx = circle_line_intersections(a, b, c, 1);
for (const ld& r : inx) VA.push_back(r);
}
}
std::sort(VA.begin(), VA.end());
int sz = VA.size();
Pos pet = ~(S.e - S.s);
Pos fug = -pet;
for (int i = 0; i < sz - 1; i++) {
ld d = VA[i + 1] - VA[i];
if (zero(d)) continue;
ld ratio = (VA[i + 1] + VA[i]) * .5;
Pos m = S.s + (S.e - S.s) * ratio;
int prev = -1, col = -1, val = N + 1, inval = N + 1;
for (int j = I - 1; j > 0; j--) {
if (C[j].type == TRI) {
int f = C[j].T.inner_check(m, pet);//centripetal
if (f == 2 || C[j].T.inner_check(m, fug) == 2) col = std::max(col, j);
if (f) prev = std::max(prev, j);
}
if (C[j].type == CIR) if (C[j].C >= m) prev = std::max(prev, j);
if (prev >= j) break;
}
for (int j = I + 1; j <= N; j++) {
if (C[j].type == TRI) {
if (C[j].T.inner_check(m, pet)) val = std::min(val, j);//centripetal
if (C[j].T.inner_check(m, fug)) inval = std::min(inval, j);//centrifugal
}
if (C[j].type == CIR) {
if (C[j].C >= m) {
val = std::min(val, j);
inval = std::min(inval, j);
}
}
if (val < N + 1 && inval < N + 1) break;
}
ld a = m.y * d * (S.e.x - S.s.x);
if (prev != -1 && prev > col) {
for (int j = I; j < inval; j++) A[j][prev] -= a;
}
for (int j = I; j < val; j++) A[j][I] += a;
}
return;
}
void green_circle(const int& I) {//refer to cki86201
vld VA = { 0, 2 * PI };
const Circle& q = C[I].C;
for (int j = 1; j <= N; j++) {
if (I == j || C[j].C == q) continue;
if (C[j].type == CIR) {
vld inx = intersection(q, C[j].C);
for (const ld& r : inx) VA.push_back(r);
}
if (C[j].type == TRI) {
vld inx;
Pos* tri[] = { &C[j].T.a, &C[j].T.b, &C[j].T.c };
for (int k = 0; k < 3; k++) {
const Pos& p1 = *tri[k], p2 = *tri[(k + 1) % 3];
inx = circle_line_intersections(p1, p2, q);
for (const ld& r : inx) VA.push_back(r);
}
}
}
std::sort(VA.begin(), VA.end());
int sz = VA.size();
for (int i = 0; i < sz - 1; i++) {
ld d = VA[i + 1] - VA[i];
if (zero(d)) continue;
ld t = (VA[i + 1] + VA[i]) * .5;
Pos R = Pos(q.r * cos(t), q.r * sin(t));
Pos pet = -R;
Pos m = q.c + R;
int prev = -1, val = N + 1;
for (int j = I - 1; j > 0; j--) {
if (C[j].type == TRI) { if (C[j].T.inner_check(m, pet)) prev = std::max(prev, j); }
if (C[j].type == CIR) {
if (C[j].C == q) continue;
if (C[j].C >= m) prev = std::max(prev, j);
}
if (prev >= j) break;
}
for (int j = I + 1; j <= N; j++) {
if (C[j].type == TRI) { if (C[j].T.inner_check(m, pet)) val = std::min(val, j); }
if (C[j].type == CIR) { if (C[j].C == q || C[j].C >= m) val = std::min(val, j); }
if (val < N + 1) break;
}
ld a = q.green(VA[i], VA[i + 1]);
if (prev != -1) {
for (int j = I; j < val; j++) A[j][prev] -= a;
}
for (int j = I; j < val; j++) A[j][I] += a;
}
return;
}
inline void solve() {
std::cin.tie(0)->sync_with_stdio(0);
std::cout.tie(0);
std::cout << std::fixed;
std::cout.precision(18);
std::cin >> N;
int t = 0, a = 0, b = 0, c = 0, d = 0, e = 0, f = 0;
for (int i = 1; i <= N; i++) {
std::cin >> t;
if (t == 1) std::cin >> a >> b >> c >> d >> e >> f;
else if (t == 2) std::cin >> a >> b >> c;
C[i] = Shape(t - 1, a, b, c, d, e, f);
}
memset(A, 0, sizeof A);
for (int i = 1; i <= N; i++) {
if (C[i].type == TRI) {
green_seg(Seg(C[i].T.a, C[i].T.b), i);
green_seg(Seg(C[i].T.b, C[i].T.c), i);
green_seg(Seg(C[i].T.c, C[i].T.a), i);
}
if (C[i].type == CIR) green_circle(i);
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= i; j++) std::cout << (long double)A[i][j] << " ";
std::cout << "\n";
}
std::cout << "\n";
return;
}
int main() { solve(); return 0; }//boj11392 Confetti refer to cki86201
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1368 KB |
Output is correct |
| 2 |
Correct |
26 ms |
1360 KB |
Output is correct |
| 3 |
Correct |
28 ms |
1372 KB |
Output is correct |
| 4 |
Correct |
26 ms |
1368 KB |
Output is correct |
| 5 |
Correct |
25 ms |
1364 KB |
Output is correct |
| 6 |
Correct |
27 ms |
1404 KB |
Output is correct |
| 7 |
Correct |
29 ms |
1364 KB |
Output is correct |
| 8 |
Correct |
26 ms |
1364 KB |
Output is correct |
| 9 |
Correct |
25 ms |
1368 KB |
Output is correct |
| 10 |
Correct |
25 ms |
1372 KB |
Output is correct |
| 11 |
Correct |
17 ms |
1372 KB |
Output is correct |
| 12 |
Correct |
20 ms |
1484 KB |
Output is correct |
| 13 |
Correct |
24 ms |
1368 KB |
Output is correct |
| 14 |
Correct |
27 ms |
1464 KB |
Output is correct |
| 15 |
Correct |
23 ms |
1496 KB |
Output is correct |
| 16 |
Correct |
20 ms |
1372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
44 ms |
1360 KB |
Output is correct |
| 3 |
Correct |
44 ms |
1360 KB |
Output is correct |
| 4 |
Correct |
61 ms |
1404 KB |
Output is correct |
| 5 |
Correct |
45 ms |
1360 KB |
Output is correct |
| 6 |
Correct |
71 ms |
1364 KB |
Output is correct |
| 7 |
Correct |
33 ms |
1412 KB |
Output is correct |
| 8 |
Correct |
54 ms |
1408 KB |
Output is correct |
| 9 |
Correct |
45 ms |
1364 KB |
Output is correct |
| 10 |
Correct |
50 ms |
1364 KB |
Output is correct |
| 11 |
Correct |
58 ms |
1384 KB |
Output is correct |
| 12 |
Correct |
64 ms |
1360 KB |
Output is correct |
| 13 |
Correct |
33 ms |
1372 KB |
Output is correct |
| 14 |
Correct |
27 ms |
1360 KB |
Output is correct |
| 15 |
Correct |
23 ms |
1408 KB |
Output is correct |
| 16 |
Correct |
31 ms |
1416 KB |
Output is correct |
| 17 |
Correct |
30 ms |
1412 KB |
Output is correct |
| 18 |
Correct |
31 ms |
1368 KB |
Output is correct |
| 19 |
Correct |
30 ms |
1412 KB |
Output is correct |
| 20 |
Correct |
34 ms |
1360 KB |
Output is correct |
