| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 998686 |
2024-06-14T14:03:11 Z |
crimson231 |
색종이 (kriii3_T) |
C++17 |
|
152 ms |
1412 KB |
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <vector>
typedef long long ll;
typedef long double ld;
typedef std::vector<ld> vld;
const ld INF = 1e17;
const ld TOL = 1e-14;
const ld PI = acosl(-1);
const int LEN = 205;
inline bool zero(const ld& x) { return -TOL <= x && x <= TOL; }
inline int sign(const ld& x) { return zero(x) ? 0 : x > 0 ? 1 : -1; }
inline ll sq(int x) { return (ll)x * x; }
inline ld norm(ld th) {
while (sign(th) < 0) th += 2 * PI;
while (sign(th - 2 * PI) >= 0) 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& scalar) const { return { x * scalar, y * scalar }; }
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 rad() const { return norm(atan2l(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 (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; }
inline bool operator > (const Pos& p) const { return r > (c - p).mag(); }
inline bool operator >= (const Pos& p) const { return (ll)r * r == (c - p).Euc(); }
ld area(const ld& lo, const ld& hi) const { return (hi - lo) * r * r; }
ld green(const ld& lo, const ld& hi) const {
Pos LO = -Pos(1, 0).rot(lo) * r;
Pos HI = Pos(1, 0).rot(hi) * r;
Pos vec = c;
return (area(lo, hi) + vec / (HI + LO)) * .5;
}
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 (0 <= a1 && a1 <= 1 && -TOL <= a2 && a2 <= 1 + TOL) return a1;
return -1;
}
vld circle_line_intersections(const Pos& s, const Pos& e, const Pos& p, const ld& r, const bool& f = 0) {
Pos vec = e - s;
Pos OM = s - p;
ld a = vec * vec;
ld b = vec * OM;
ld c = OM * OM - r * r;
ld J = b * b - a * c;
if (sign(J) < 0) return {};
ld det = sqrtl(std::max((ld)0, J));
ld lo = (-b - det) / (2 * a);
ld hi = (-b + det) / (2 * 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 = [&](const ld& rt) -> ld {
Pos v = s + (e - s) * rt;
return (v - p).rad();
};
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 (S.s / S.e == 0) return;
vld VA = { 0, 1 };
const Pos& a = S.s, b = S.e;
for (int j = 0; 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;
for (int k = 0; k < 3; k++) {
inx = circle_line_intersections(a, b, c.c, c.r, 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, inval = N;
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 && col >= 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 && inval < N) break;
}
ld a = S.green(d);
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 = 0; 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.c, q.r);
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, 0).rot(t);
Pos pet = -R;
Pos m = q.c + R;
int prev = -1, val = N;
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) 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(15);
std::cin >> N;
int t = 0, a = 0, b = 0, c = 0, d = 0, e = 0, f = 0;
for (int i = 0; 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 = 0; 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 = 0; i < N; i++) {
for (int j = 0; 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 |
Incorrect |
114 ms |
1364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
152 ms |
1412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
