QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#550722 | #9253. Prism Palace | ucup-team3646# | AC ✓ | 176ms | 9456kb | C++17 | 16.5kb | 2024-09-07 14:03:05 | 2024-09-07 14:03:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#include <bits/stdc++.h>
using namespace std;
using Real = long double;
using Point = complex<Real>;
const Real EPS = 1e-9, PI = acos(-1);
inline bool eq(Real a, Real b) {
return fabs(b - a) < EPS;
}
Point operator*(const Point &p, const Real &d) {
return Point(real(p) * d, imag(p) * d);
}
istream &operator>>(istream &is, Point &p) {
Real a, b;
is >> a >> b;
p = Point(a, b);
return is;
}
ostream &operator<<(ostream &os, Point &p) {
return os << fixed << setprecision(10) << p.real() << " " << p.imag();
}
// 点 p を反時計回りに theta 回転
Point rotate(Real theta, const Point &p) {
return Point(
cos(theta) * p.real() - sin(theta) * p.imag(), sin(theta) * p.real() + cos(theta) * p.imag());
}
Real radian_to_degree(Real r) {
return (r * 180.0 / PI);
}
Real degree_to_radian(Real d) {
return (d * PI / 180.0);
}
// a-b-c の角度のうち小さい方を返す
Real get_angle(const Point &a, const Point &b, const Point &c) {
const Point v(a - b), w(c - b);
Real alpha = atan2(v.imag(), v.real()), beta = atan2(w.imag(), w.real());
if (alpha > beta) swap(alpha, beta);
Real theta = (beta - alpha);
return min(theta, 2 * acos(-1) - theta);
}
namespace std {
bool operator<(const Point &a, const Point &b) {
return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
}
} // namespace std
struct Line {
Point a, b;
Line() = default;
Line(Point a, Point b) : a(a), b(b) {}
Line(Real A, Real B, Real C) // Ax + By = C
{
if (eq(A, 0)) a = Point(0, C / B), b = Point(1, C / B);
else if (eq(B, 0)) b = Point(C / A, 0), b = Point(C / A, 1);
else a = Point(0, C / B), b = Point(C / A, 0);
}
friend ostream &operator<<(ostream &os, Line &p) { return os << p.a << " to " << p.b; }
friend istream &operator>>(istream &is, Line &a) { return is >> a.a >> a.b; }
};
struct Segment : Line {
Segment() = default;
Segment(Point a, Point b) : Line(a, b) {}
};
struct Circle {
Point p;
Real r;
Circle() = default;
Circle(Point p, Real r) : p(p), r(r) {}
};
using Points = vector<Point>;
using Polygon = vector<Point>;
using Segments = vector<Segment>;
using Lines = vector<Line>;
using Circles = vector<Circle>;
Real cross(const Point &a, const Point &b) {
return real(a) * imag(b) - imag(a) * real(b);
}
Real dot(const Point &a, const Point &b) {
return real(a) * real(b) + imag(a) * imag(b);
}
// 点の回転方向
int ccw(const Point &a, Point b, Point c) {
b = b - a, c = c - a;
if (cross(b, c) > EPS) return +1; // "COUNTER_CLOCKWISE"
if (cross(b, c) < -EPS) return -1; // "CLOCKWISE"
if (dot(b, c) < 0) return +2; // "ONLINE_BACK"
if (norm(b) < norm(c)) return -2; // "ONLINE_FRONT"
return 0; // "ON_SEGMENT"
}
// 平行判定
bool parallel(const Line &a, const Line &b) {
return eq(cross(a.b - a.a, b.b - b.a), 0.0);
}
// 垂直判定
bool orthogonal(const Line &a, const Line &b) {
return eq(dot(a.a - a.b, b.a - b.b), 0.0);
}
// 射影
// 直線 l に p から垂線を引いた交点を求める
Point projection(const Line &l, const Point &p) {
double t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
return l.a + (l.a - l.b) * t;
}
Point projection(const Segment &l, const Point &p) {
double t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
return l.a + (l.a - l.b) * t;
}
// 反射
// 直線 l を対称軸として点 p と線対称にある点を求める
Point reflection(const Line &l, const Point &p) {
return p + (projection(l, p) - p) * 2.0;
}
bool intersect(const Line &l, const Point &p) {
return abs(ccw(l.a, l.b, p)) != 1;
}
bool intersect(const Line &l, const Line &m) {
return abs(cross(l.b - l.a, m.b - m.a)) > EPS || abs(cross(l.b - l.a, m.b - l.a)) < EPS;
}
bool intersect(const Segment &s, const Point &p) {
return ccw(s.a, s.b, p) == 0;
}
bool intersect(const Line &l, const Segment &s) {
return cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < EPS;
}
Real distance(const Line &l, const Point &p);
bool intersect(const Circle &c, const Line &l) {
return distance(l, c.p) <= c.r + EPS;
}
bool intersect(const Circle &c, const Point &p) {
return abs(abs(p - c.p) - c.r) < EPS;
}
bool intersect(const Segment &s, const Segment &t) {
return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}
int intersect(const Circle &c, const Segment &l) {
if (norm(projection(l, c.p) - c.p) - c.r * c.r > EPS) return 0;
auto d1 = abs(c.p - l.a), d2 = abs(c.p - l.b);
if (d1 < c.r + EPS && d2 < c.r + EPS) return 0;
if (d1 < c.r - EPS && d2 > c.r + EPS || d1 > c.r + EPS && d2 < c.r - EPS) return 1;
const Point h = projection(l, c.p);
if (dot(l.a - h, l.b - h) < 0) return 2;
return 0;
}
int intersect(Circle c1, Circle c2) {
if (c1.r < c2.r) swap(c1, c2);
Real d = abs(c1.p - c2.p);
if (c1.r + c2.r < d) return 4;
if (eq(c1.r + c2.r, d)) return 3;
if (c1.r - c2.r < d) return 2;
if (eq(c1.r - c2.r, d)) return 1;
return 0;
}
Real distance(const Point &a, const Point &b) {
return abs(a - b);
}
Real distance(const Line &l, const Point &p) {
return abs(p - projection(l, p));
}
Real distance(const Line &l, const Line &m) {
return intersect(l, m) ? 0 : distance(l, m.a);
}
Real distance(const Segment &s, const Point &p) {
Point r = projection(s, p);
if (intersect(s, r)) return abs(r - p);
return min(abs(s.a - p), abs(s.b - p));
}
Real distance(const Segment &a, const Segment &b) {
if (intersect(a, b)) return 0;
return min({distance(a, b.a), distance(a, b.b), distance(b, a.a), distance(b, a.b)});
}
Real distance(const Line &l, const Segment &s) {
if (intersect(l, s)) return 0;
return min(distance(l, s.a), distance(l, s.b));
}
Point crosspoint(const Line &l, const Line &m) {
Real A = cross(l.b - l.a, m.b - m.a);
Real B = cross(l.b - l.a, l.b - m.a);
if (eq(abs(A), 0.0) && eq(abs(B), 0.0)) return m.a;
return m.a + (m.b - m.a) * B / A;
}
Point crosspoint(const Segment &l, const Segment &m) {
return crosspoint(Line(l), Line(m));
}
pair<Point, Point> crosspoint(const Circle &c, const Line l) {
Point pr = projection(l, c.p);
Point e = (l.b - l.a) / abs(l.b - l.a);
if (eq(distance(l, c.p), c.r)) return {pr, pr};
double base = sqrt(c.r * c.r - norm(pr - c.p));
return {pr - e * base, pr + e * base};
}
pair<Point, Point> crosspoint(const Circle &c, const Segment &l) {
Line aa = Line(l.a, l.b);
if (intersect(c, l) == 2) return crosspoint(c, aa);
auto ret = crosspoint(c, aa);
if (dot(l.a - ret.first, l.b - ret.first) < 0) ret.second = ret.first;
else ret.first = ret.second;
return ret;
}
pair<Point, Point> crosspoint(const Circle &c1, const Circle &c2) {
Real d = abs(c1.p - c2.p);
Real a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d));
Real t = atan2(c2.p.imag() - c1.p.imag(), c2.p.real() - c1.p.real());
Point p1 = c1.p + Point(cos(t + a) * c1.r, sin(t + a) * c1.r);
Point p2 = c1.p + Point(cos(t - a) * c1.r, sin(t - a) * c1.r);
return {p1, p2};
}
// 点 p を通る円 c の接線
pair<Point, Point> tangent(const Circle &c1, const Point &p2) {
return crosspoint(c1, Circle(p2, sqrt(norm(c1.p - p2) - c1.r * c1.r)));
}
// 円 c1, c2 の共通接線
Lines tangent(Circle c1, Circle c2) {
Lines ret;
if (c1.r < c2.r) swap(c1, c2);
Real g = norm(c1.p - c2.p);
if (eq(g, 0)) return ret;
Point u = (c2.p - c1.p) / sqrt(g);
Point v = rotate(PI * 0.5, u);
for (int s : {-1, 1}) {
Real h = (c1.r + s * c2.r) / sqrt(g);
if (eq(1 - h * h, 0)) {
ret.emplace_back(c1.p + u * c1.r, c1.p + (u + v) * c1.r);
} else if (1 - h * h > 0) {
Point uu = u * h, vv = v * sqrt(1 - h * h);
ret.emplace_back(c1.p + (uu + vv) * c1.r, c2.p - (uu + vv) * c2.r * s);
ret.emplace_back(c1.p + (uu - vv) * c1.r, c2.p - (uu - vv) * c2.r * s);
}
}
return ret;
}
// 凸性判定
bool is_convex(const Polygon &p) {
int n = (int)p.size();
for (int i = 0; i < n; i++) {
if (ccw(p[(i + n - 1) % n], p[i], p[(i + 1) % n]) == -1) return false;
}
return true;
}
// 凸包
// 注意 : 次のようなケースで壊れることが確認されています。
// 5
// 0 0
// -1 1
// -2 -1
// 1 -2
// 2 0
Polygon convex_hull(Polygon &p) {
int n = (int)p.size(), k = 0;
if (n <= 2) return p;
sort(p.begin(), p.end());
vector<Point> ch(2 * n);
for (int i = 0; i < n; ch[k++] = p[i++]) {
while (k >= 2 && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS) --k;
}
for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) {
while (k >= t && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS) --k;
}
ch.resize(k - 1);
return ch;
}
// 多角形と点の包含判定
enum { OUT, ON, IN };
int contains(const Polygon &Q, const Point &p) {
bool in = false;
for (int i = 0; i < Q.size(); i++) {
Point a = Q[i] - p, b = Q[(i + 1) % Q.size()] - p;
if (a.imag() > b.imag()) swap(a, b);
if (a.imag() <= 0 && 0 < b.imag() && cross(a, b) < 0) in = !in;
if (cross(a, b) == 0 && dot(a, b) <= 0) return ON;
}
return in ? IN : OUT;
}
// 線分の重複除去
void merge_segments(vector<Segment> &segs) {
auto merge_if_able = [](Segment &s1, const Segment &s2) {
if (abs(cross(s1.b - s1.a, s2.b - s2.a)) > EPS) return false;
if (ccw(s1.a, s2.a, s1.b) == 1 || ccw(s1.a, s2.a, s1.b) == -1) return false;
if (ccw(s1.a, s1.b, s2.a) == -2 || ccw(s2.a, s2.b, s1.a) == -2) return false;
s1 = Segment(min(s1.a, s2.a), max(s1.b, s2.b));
return true;
};
for (int i = 0; i < segs.size(); i++) {
if (segs[i].b < segs[i].a) swap(segs[i].a, segs[i].b);
}
for (int i = 0; i < segs.size(); i++) {
for (int j = i + 1; j < segs.size(); j++) {
if (merge_if_able(segs[i], segs[j])) {
segs[j--] = segs.back(), segs.pop_back();
}
}
}
}
// 線分アレンジメント
// 任意の2線分の交点を頂点としたグラフを構築する
vector<vector<int>> segment_arrangement(vector<Segment> &segs, vector<Point> &ps) {
vector<vector<int>> g;
int N = (int)segs.size();
for (int i = 0; i < N; i++) {
ps.emplace_back(segs[i].a);
ps.emplace_back(segs[i].b);
for (int j = i + 1; j < N; j++) {
const Point p1 = segs[i].b - segs[i].a;
const Point p2 = segs[j].b - segs[j].a;
if (cross(p1, p2) == 0) continue;
if (intersect(segs[i], segs[j])) {
ps.emplace_back(crosspoint(segs[i], segs[j]));
}
}
}
sort(begin(ps), end(ps));
ps.erase(unique(begin(ps), end(ps)), end(ps));
int M = (int)ps.size();
g.resize(M);
for (int i = 0; i < N; i++) {
vector<int> vec;
for (int j = 0; j < M; j++) {
if (intersect(segs[i], ps[j])) {
vec.emplace_back(j);
}
}
for (int j = 1; j < vec.size(); j++) {
g[vec[j - 1]].push_back(vec[j]);
g[vec[j]].push_back(vec[j - 1]);
}
}
return (g);
}
// 凸多角形の切断
// 直線 l.a-l.b で切断しその左側にできる凸多角形を返す
Polygon convex_cut(const Polygon &U, Line l) {
Polygon ret;
for (int i = 0; i < U.size(); i++) {
Point now = U[i], nxt = U[(i + 1) % U.size()];
if (ccw(l.a, l.b, now) != -1) ret.push_back(now);
if (ccw(l.a, l.b, now) * ccw(l.a, l.b, nxt) < 0) {
ret.push_back(crosspoint(Line(now, nxt), l));
}
}
return (ret);
}
// 多角形の面積
Real area(const Polygon &p) {
Real A = 0;
for (int i = 0; i < p.size(); ++i) {
A += cross(p[i], p[(i + 1) % p.size()]);
}
return A * 0.5;
}
// 円と多角形の共通部分の面積
Real area(const Polygon &p, const Circle &c) {
if (p.size() < 3) return 0.0;
function<Real(Circle, Point, Point)> cross_area = [&](const Circle &c, const Point &a,
const Point &b) {
Point va = c.p - a, vb = c.p - b;
Real f = cross(va, vb), ret = 0.0;
if (eq(f, 0.0)) return ret;
if (max(abs(va), abs(vb)) < c.r + EPS) return f;
if (distance(Segment(a, b), c.p) > c.r - EPS) return c.r * c.r * arg(vb * conj(va));
auto u = crosspoint(c, Segment(a, b));
vector<Point> tot{a, u.first, u.second, b};
for (int i = 0; i + 1 < tot.size(); i++) {
ret += cross_area(c, tot[i], tot[i + 1]);
}
return ret;
};
Real A = 0;
for (int i = 0; i < p.size(); i++) {
A += cross_area(c, p[i], p[(i + 1) % p.size()]);
}
return A;
}
// 凸多角形の直径(最遠頂点対間距離)
Real convex_diameter(const Polygon &p) {
int N = (int)p.size();
int is = 0, js = 0;
for (int i = 1; i < N; i++) {
if (p[i].imag() > p[is].imag()) is = i;
if (p[i].imag() < p[js].imag()) js = i;
}
Real maxdis = norm(p[is] - p[js]);
int maxi, maxj, i, j;
i = maxi = is;
j = maxj = js;
do {
if (cross(p[(i + 1) % N] - p[i], p[(j + 1) % N] - p[j]) >= 0) {
j = (j + 1) % N;
} else {
i = (i + 1) % N;
}
if (norm(p[i] - p[j]) > maxdis) {
maxdis = norm(p[i] - p[j]);
maxi = i;
maxj = j;
}
} while (i != is || j != js);
return sqrt(maxdis);
}
// 最近点対
Real closest_pair(Points ps) {
if (ps.size() <= 1) throw(0);
sort(begin(ps), end(ps));
auto compare_y = [&](const Point &a, const Point &b) { return imag(a) < imag(b); };
vector<Point> beet(ps.size());
const Real INF = 1e18;
function<Real(int, int)> rec = [&](int left, int right) {
if (right - left <= 1) return INF;
int mid = (left + right) >> 1;
auto x = real(ps[mid]);
auto ret = min(rec(left, mid), rec(mid, right));
inplace_merge(begin(ps) + left, begin(ps) + mid, begin(ps) + right, compare_y);
int ptr = 0;
for (int i = left; i < right; i++) {
if (abs(real(ps[i]) - x) >= ret) continue;
for (int j = 0; j < ptr; j++) {
auto luz = ps[i] - beet[ptr - j - 1];
if (imag(luz) >= ret) break;
ret = min(ret, abs(luz));
}
beet[ptr++] = ps[i];
}
return ret;
};
return rec(0, (int)ps.size());
}
// 平面グラフを多角形に分割する (基本的に反時計回り、外平面のみ時計回り)
// graph は単純無向グラフを想定 (u-v <=> v-u)。
// 多重辺、有向グラフなど変なグラフを入れると壊れるはず。非連結グラフは問題なし
vector<vector<int>> decompose_to_cycle(const vector<vector<int>> &graph, const vector<Point> &pos) {
assert(graph.size() == pos.size());
int n = graph.size();
int m = 0;
map<array<int, 2>, int> mp;
vector<array<int, 2>> edge;
for (int i = 0; i < n; ++i) {
for (auto ni : graph[i]) {
mp[{i, ni}] = m++;
edge.push_back({i, ni});
}
}
vector<int> nex(m, -1);
for (int i = 0; i < n; ++i) {
if (graph[i].empty()) continue;
vector<pair<long double, int>> adj;
for (int ni : graph[i]) {
Point diff = pos[ni] - pos[i];
assert(!eq(abs(diff), 0.0));
adj.push_back({arg(diff), ni});
}
sort(adj.begin(), adj.end());
int siz = adj.size();
adj.emplace_back(adj[0]);
adj[siz].first += 2 * PI;
for (int j = 0; j < siz; ++j) {
auto [arg0, to] = adj[j];
auto [arg1, from] = adj[j + 1];
int ein = mp[{from, i}];
int eout = mp[{i, to}];
nex[ein] = eout;
}
}
vector<vector<int>> ret;
vector<bool> used(m, false);
for (int i = 0; i < m; ++i) {
if (used[i]) continue;
vector<int> tmp;
int now = i;
while (!used[now]) {
used[now] = true;
tmp.emplace_back(edge[now][0]);
now = nex[now];
}
ret.emplace_back(tmp);
}
return ret;
}
/*-- main --*/
using ll = long long;
int main() {
ll N; cin >> N;
vector<Point> poly(N);
for (int i = 0; i < N; ++i) {
Real x, y; cin >> x >> y;
poly[i] = Point(x, y);
}
Real sum = 0.0;
for (int i = 0; i < N; ++i) {
Real left = get_angle(poly[(i-1+N)%N], poly[i%N], poly[(i+1)%N]);
Real right = get_angle(poly[i%N], poly[(i+1)%N], poly[(i+2)%N]);
sum += max(PI - (left + right), Real(0.0));
// cout << i << " " << left / PI * 180 << " " << right / PI * 180 << endl;
// cout << (left + right) / PI * 180 << endl;
}
Real prob = sum / PI;
cout << fixed << setprecision(20);
cout << prob << endl;
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3928kb
input:
3 0 0 1 0 0 1
output:
0.99999999999999992199
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
4 0 0 0 1 1 1 1 0
output:
0.00000000000000007813
result:
ok found '0.0000000', expected '0.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
4 0 0 0 3 1 2 1 1
output:
0.50000000000000005849
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 176ms
memory: 9456kb
input:
199996 719157942 80035870 719158808 80033199 719160795 80027070 719162868 80020675 719165635 80012139 719166422 80009711 719166927 80008153 719168388 80003645 719168539 80003179 719168806 80002355 719168864 80002176 719169119 80001389 719171067 79995376 719173806 79986921 719175195 79982633 71917686...
output:
0.00007771680349044340
result:
ok found '0.0000777', expected '0.0000777', error '0.0000000'
Test #5:
score: 0
Accepted
time: 174ms
memory: 9228kb
input:
199999 521578765 315995242 521578784 315995230 521585008 315991299 521590377 315987908 521597318 315983524 521606119 315977965 521610976 315974897 521614329 315972779 521622922 315967351 521631939 315961655 521636172 315958981 521638241 315957674 521643115 315954595 521650976 315949629 521656567 315...
output:
0.00009653217935267606
result:
ok found '0.0000965', expected '0.0000965', error '0.0000000'
Test #6:
score: 0
Accepted
time: 175ms
memory: 9408kb
input:
200000 88808852 208512084 88810113 208513562 88812008 208515783 88812543 208516410 88816806 208521406 88824507 208530431 88825624 208531740 88831723 208538887 88834262 208541862 88838287 208546578 88845440 208554959 88848801 208558897 88855564 208566821 88856869 208568350 88862876 208575388 88868324...
output:
0.00007437370129564858
result:
ok found '0.0000744', expected '0.0000744', error '0.0000000'
Test #7:
score: 0
Accepted
time: 175ms
memory: 9408kb
input:
199998 2857588 37580055 2857908 37582176 2857951 37582461 2858026 37582958 2859295 37591366 2859678 37593903 2860879 37601857 2862301 37611272 2862330 37611464 2863054 37616255 2864429 37625353 2865434 37632002 2865585 37633001 2867092 37642971 2867321 37644486 2867870 37648118 2868343 37651247 2868...
output:
0.00006753968344456512
result:
ok found '0.0000675', expected '0.0000675', error '0.0000000'
Test #8:
score: 0
Accepted
time: 175ms
memory: 9328kb
input:
199999 487716180 333296644 487720319 333294576 487721706 333293883 487731571 333288954 487734599 333287441 487742738 333283374 487744419 333282534 487746174 333281657 487748301 333280594 487750462 333279514 487754846 333277323 487759670 333274912 487762097 333273699 487764676 333272410 487772963 333...
output:
0.00007069670178668047
result:
ok found '0.0000707', expected '0.0000707', error '0.0000000'
Extra Test:
score: 0
Extra Test Passed