QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#534278 | #7310. Circular Sectors | mshcherba | WA | 9ms | 4320kb | C++20 | 10.0kb | 2024-08-26 23:25:40 | 2024-08-26 23:25:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef long double db;
const db PI = acos(-1.0);
const db EPS = 1e-9;
struct Pt
{
db x, y;
Pt operator+(const Pt& p) const
{
return {x + p.x, y + p.y};
}
Pt operator-(const Pt& p) const
{
return {x - p.x, y - p.y};
}
Pt operator*(db d) const
{
return {x * d, y * d};
}
Pt operator/(db d) const
{
return {x / d, y / d};
}
};
db sq(const Pt& p)
{
return p.x * p.x + p.y * p.y;
}
db abs(const Pt& p)
{
return sqrt(sq(p));
}
int sgn(db x)
{
return (EPS < x) - (x < -EPS);
}
// Returns `p` rotated counter-clockwise by `a`
Pt rot(const Pt& p, db a)
{
db co = cos(a), si = sin(a);
return {p.x * co - p.y * si,
p.x * si + p.y * co};
}
// Returns `p` rotated counter-clockwise by 90 degrees
Pt perp(const Pt& p)
{
return {-p.y, p.x};
}
db dot(const Pt& p, const Pt& q)
{
return p.x * q.x + p.y * q.y;
}
// Returns the angle between `p` and `q` in [0, pi]
db angle(const Pt& p, const Pt& q)
{
return acos(clamp(dot(p, q) / abs(p) /
abs(q), (db)-1.0, (db)1.0));
}
db cross(const Pt& p, const Pt& q)
{
return p.x * q.y - p.y * q.x;
}
// Positive if R is on the left side of PQ,
// negative on the right side,
// and zero if R is on the line containing PQ
db orient(const Pt& p, const Pt& q, const Pt& r)
{
return cross(q - p, r - p) / abs(q - p);
}
// Checks if argument of `p` is in [-pi, 0)
bool half(const Pt& p)
{
assert(sgn(p.x) != 0 || sgn(p.y) != 0);
return sgn(p.y) == -1 ||
(sgn(p.y) == 0 && sgn(p.x) == -1);
}
void polarSortAround(const Pt& o, vector<Pt>& v)
{
sort(ALL(v), [o](Pt p, Pt q)
{
p = p - o;
q = q - o;
bool hp = half(p), hq = half(q);
if (hp != hq)
return hp < hq;
int s = sgn(cross(p, q));
if (s != 0)
return s == 1;
return sq(p) < sq(q);
});
}
ostream& operator<<(ostream& os, const Pt& p)
{
return os << "(" << p.x << "," << p.y << ")";
}
struct Line
{
// Equation of the line is dot(n, p) + c = 0
Pt n;
db c;
Line() {}
Line (const Pt& _n, db _c): n(_n), c(_c) {}
// n is the normal vector to the left of PQ
Line(const Pt& p, const Pt& q):
n(perp(q - p)), c(-dot(n, p)) {}
// The "positive side": dot(n, p) + c > 0
// The "negative side": dot(n, p) + c < 0
db side(const Pt& p) const
{
return dot(n, p) + c;
}
db dist(const Pt& p) const
{
return abs(side(p)) / abs(n);
}
db sqDist(const Pt& p) const
{
return side(p) * side(p) / (db)sq(n);
}
Line perpThrough(const Pt& p) const
{
return {p, p + n};
}
bool cmpProj(const Pt& p, const Pt& q) const
{
return sgn(cross(p, n) - cross(q, n)) < 0;
}
Pt proj(const Pt& p) const
{
return p - n * side(p) / sq(n);
}
Pt reflect(const Pt& p) const
{
return p - n * 2 * side(p) / sq(n);
}
};
bool parallel(const Line& l1, const Line& l2)
{
return sgn(cross(l1.n, l2.n)) == 0;
}
Pt inter(const Line& l1, const Line& l2)
{
db d = cross(l1.n, l2.n);
assert(sgn(d) != 0);
return perp(l2.n * l1.c - l1.n * l2.c) / d;
}
// Checks if `p` is in the disk (the region in a plane
// bounded by a circle) of diameter [ab]
bool inDisk(const Pt& a, const Pt& b, const Pt& p)
{
return sgn(dot(a - p, b - p)) <= 0;
}
// Checks if `p` lies on segment [ab]
bool onSegment(const Pt& a, const Pt& b, const Pt& p)
{
return sgn(orient(a, b, p)) == 0 && inDisk(a, b, p);
}
// Checks if the segments [ab] and [cd] intersect
// properly (their intersection is one point
// which is not an endpoint of either segment)
bool properInter(const Pt& a, const Pt& b, const Pt& c, const Pt& d)
{
db oa = orient(c, d, a);
db ob = orient(c, d, b);
db oc = orient(a, b, c);
db od = orient(a, b, d);
return sgn(oa) * sgn(ob) == -1 && sgn(oc) * sgn(od) == -1;
}
// Returns the distance between [ab] and `p`
db segPt(const Pt& a, const Pt& b, const Pt& p)
{
Line l(a, b);
assert(sgn(sq(l.n)) != 0);
if (l.cmpProj(a, p) && l.cmpProj(p, b))
return l.dist(p);
return min(abs(p - a), abs(p - b));
}
// Returns the distance between [ab] and [cd]
db segSeg(const Pt& a, const Pt& b, const Pt& c, const Pt& d)
{
if (properInter(a, b, c, d))
return 0;
return min({segPt(a, b, c), segPt(a, b, d),
segPt(c, d, a), segPt(c, d, b)});
}
// Returns the circumcenter of triangle abc.
// The circumcircle of a triangle is a circle that passes through all three vertices.
Pt circumCenter(const Pt& a, Pt b, Pt c)
{
b = b - a;
c = c - a;
assert(sgn(cross(b, c)) != 0);
return a + perp(b * sq(c) - c * sq(b)) / cross(b, c) / 2;
}
// Returns circle-line intersection points
vector<Pt> circleLine(const Pt& o, db r, const Line& l)
{
db h2 = r * r - l.sqDist(o);
if (sgn(h2) == -1)
return {};
Pt p = l.proj(o);
if (sgn(h2) == 0)
return {p};
Pt h = perp(l.n) * sqrt(h2) / abs(l.n);
return {p - h, p + h};
}
// Returns circle-circle intersection points
vector<Pt> circleCircle(const Pt& o1, db r1, const Pt& o2, db r2)
{
Pt d = o2 - o1;
db d2 = sq(d);
if (sgn(sqrt(d2)) == 0)
{
#warning
// assuming the circles don't coincide
cerr << d2 << endl;
assert(sgn(r2 - r1) != 0);
return {};
}
db pd = (d2 + r1 * r1 - r2 * r2) / 2;
db h2 = r1 * r1 - pd * pd / d2;
if (sgn(h2) == -1)
return {};
Pt p = o1 + d * pd / d2;
if (sgn(h2) == 0)
return {p};
Pt h = perp(d) * sqrt(h2 / d2);
return {p - h, p + h};
}
mt19937 rng;
int rand(int a, int b)
{
return a + rng() % (b - a);
}
void perturb(Pt& p)
{
const int C = 1e6;
p.x += 1e-8 * rand(-C, C + 1) / C;
p.y += 1e-8 * rand(-C, C + 1) / C;
}
struct Sector
{
Pt c;
db r, s, theta;
Line l[2];
void read()
{
cin >> c.x >> c.y >> r >> s >> theta;
}
bool contains(const Pt& p) const
{
db d = abs(p - c);
if (sgn(d) == 0)
return true;
if (sgn(d - r) > 0)
return false;
db phi = atan2(p.y - c.y, p.x - c.x);
FOR(i, 0, 3)
{
if (sgn(s - phi) <= 0 && sgn(phi - (s + theta)) <= 0)
return true;
phi += 2 * PI;
}
return false;
}
};
vector<Pt> getPtsOnSeg(const Pt& p1, const Pt& p2, const Sector& s)
{
Line l(p1, p2);
vector<Pt> res = {p1, p2};
vector<Pt> qq = circleLine(s.c, s.r, l);
FOR(i, 0, 2)
{
if (parallel(l, s.l[i]))
continue;
qq.PB(inter(l, s.l[i]));
}
for (const Pt& q : qq)
{
if (onSegment(p1, p2, q) && s.contains(q))
res.PB(q);
}
sort(ALL(res), [&](const Pt& q1, const Pt& q2)
{
return sgn(abs(q1 - p1) - abs(q2 - p1)) < 0;
});
return res;
}
vector<db> getPhisOnArc(const Sector& s1, const Sector& s2)
{
vector<Pt> qq = circleCircle(s1.c, s1.r, s2.c, s2.r);
FOR(i, 0, 2)
{
vector<Pt> qqq = circleLine(s1.c, s1.r, s2.l[i]);
qq.insert(qq.end(), ALL(qqq));
}
vector<db> res = {s1.s, s1.s + s1.theta};
for (const Pt& q : qq)
{
if (!s1.contains(q) || !s2.contains(q))
continue;
db phi = atan2(q.y - s1.c.y, q.x - s1.c.x);
while (sgn(s1.s - phi) > 0)
phi += 2 * PI;
assert(sgn(s1.s - phi) <= 0 && sgn(phi - (s1.s + s1.theta)) <= 0);
res.PB(phi);
}
sort(ALL(res));
return res;
}
vector<pair<Pt, Pt>> getUsefulOnSeg(const Sector& s2, const vector<Pt>& v)
{
vector<pair<Pt, Pt>> res;
FOR(i, 0, SZ(v) - 1)
{
if (!s2.contains((v[i] + v[i + 1]) / 2))
res.PB({v[i], v[i + 1]});
}
return res;
}
vector<pair<db, db>> getUsefulOnArc(const Sector& s1, const Sector& s2)
{
const auto& v = getPhisOnArc(s1, s2);
vector<pair<db, db>> res;
FOR(i, 0, SZ(v) - 1)
{
db phi = (v[i] + v[i + 1]) / 2;
const Pt& p = {s1.c.x + s1.r * cos(phi), s1.c.y + s1.r * sin(phi)};
if (!s2.contains(p))
res.PB({v[i], v[i + 1]});
}
return res;
}
int n;
void solve()
{
vector<Sector> sectors(n);
vector<vector<Pt>> p(n, vector<Pt>(2));
FOR(i, 0, n)
{
Sector& sector = sectors[i];
sector.read();
perturb(sector.c);
FOR(j, 0, 2)
{
db phi = sector.s + j * sector.theta;
p[i][j] = {sector.c.x + sector.r * cos(phi), sector.c.y + sector.r * sin(phi)};
sector.l[j] = {sector.c, p[i][j]};
}
}
db ans = 0;
FOR(i, 0, n)
{
vector<pair<Pt, int>> eventsSeg[2] = {
{{sectors[i].c, 1}, {p[i][0], -1}},
{{sectors[i].c, 1}, {p[i][1], -1}}};
vector<pair<db, int>> eventsArc = {{sectors[i].s, 1}, {sectors[i].s + sectors[i].theta, -1}};
FOR(j, 0, n)
{
if (i == j)
continue;
FOR(ii, 0, 2)
{
auto ptsOnSeg = getPtsOnSeg(sectors[i].c, p[i][ii], sectors[j]);
auto usefulOnSeg = getUsefulOnSeg(sectors[j], ptsOnSeg);
for (const auto& [p1, p2] : usefulOnSeg)
{
eventsSeg[ii].PB({p1, 1});
eventsSeg[ii].PB({p2, -1});
}
}
auto usefulOnArc = getUsefulOnArc(sectors[i], sectors[j]);
for (auto [phi1, phi2] : usefulOnArc)
{
eventsArc.PB({phi1, 1});
eventsArc.PB({phi2, -1});
}
}
FOR(ii, 0, 2)
{
sort(ALL(eventsSeg[ii]), [&](const pair<Pt, int>& p1, const pair<Pt, int>& p2)
{
return sgn(abs(p1.F - sectors[i].c) - abs(p2.F - sectors[i].c)) < 0;
});
int bal = 0;
db sum = 0;
FOR(k, 0, SZ(eventsSeg[ii]))
{
bal += eventsSeg[ii][k].S;
if (bal == n)
{
sum += cross(eventsSeg[ii][k].F, eventsSeg[ii][k + 1].F);
}
}
ans += (ii == 0 ? 1 : -1) * sum;
}
sort(ALL(eventsArc));
int bal = 0;
FOR(k, 0, SZ(eventsArc))
{
bal += eventsArc[k].S;
if (bal == n)
{
db phi1 = eventsArc[k].F, phi2 = eventsArc[k + 1].F;
ans += sectors[i].r * (sectors[i].c.x * (sin(phi2) - sin(phi1))
- sectors[i].c.y * (cos(phi2) - cos(phi1))
+ sectors[i].r * (phi2 - phi1));
}
}
}
ans /= 2;
cout << ans << "\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(10);
while (cin >> n)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4208kb
input:
2 -3 -5 5 0.705 0.217 -5 1 4 3.070 4.136 1 -4 -4 1 0.485 2.260 3 4 4 4 4.266 4.673 2 -4 5 0.353 5.565 -2 1 3 3.974 0.207
output:
35.8005000000 1.1300000000 106.4449314242
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 2ms
memory: 4228kb
input:
2 -2 -1 5 2.250 0.555 -3 0 2 2.189 0.788 2 -5 1 5 0.432 1.643 3 5 5 4.779 2.014 2 2 0 3 4.194 2.691 4 -3 4 0.998 5.376 2 -3 1 4 5.841 2.968 -4 -3 2 4.151 4.029 2 4 -1 5 2.416 2.385 5 0 3 5.315 2.683 2 -2 0 2 3.972 1.255 2 -5 2 0.912 5.211 2 1 0 4 2.826 3.794 -2 -3 1 3.335 3.836 2 -5 4 2 2.496 2.273 ...
output:
6.9375000000 45.7125000000 43.5339209128 31.8020000000 41.8860000000 12.9320000000 31.7131023705 9.8900000000 3.8115000000 26.7900000000 37.1875000000 10.7005000035 31.4235000000 47.6640000000 25.4565000000 54.0135950822 47.2744417629 7.0325000000 10.0475000000 49.4407408731 12.5750972567 34.6755000...
result:
ok 250 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 4228kb
input:
3 1 -1 5 3.089 5.717 -2 0 2 4.806 3.257 0 -3 2 5.069 3.049 3 -2 -4 2 4.616 2.875 2 -2 4 5.798 3.097 -1 2 1 0.064 5.418 3 -1 1 2 4.105 3.883 0 5 4 1.936 4.292 2 -5 2 0.278 4.486 3 3 -5 5 3.208 4.696 -2 -4 3 3.609 0.906 -2 4 3 3.796 4.334 3 0 -1 1 4.313 0.711 2 -2 1 2.962 0.344 -4 2 5 2.524 3.043 3 -1...
output:
74.1578797486 33.2350000000 47.7494614476 82.2800000000 38.5650000000 57.2875000000 16.8875000000 30.8124663184 18.2661373709 43.2646347616 42.4942175211 26.1327491637 26.4045000000 30.1067281133 48.9370000000 23.1395000000 56.7305000000 68.3693801517 56.9404374083 26.6910000000 36.5250853849 21.669...
result:
ok 166 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 4320kb
input:
4 4 3 4 1.727 2.114 -5 3 2 5.010 2.690 -1 1 5 4.078 2.852 1 5 5 2.974 4.884 4 3 4 1 5.626 2.021 2 -4 1 1.241 0.231 4 -4 5 0.323 5.472 -2 5 2 2.648 1.031 4 -1 -1 2 0.156 3.062 2 2 1 1.127 4.124 5 3 5 1.105 5.179 4 2 3 3.363 4.235 4 -2 -3 3 1.013 4.047 0 -5 5 1.829 4.952 -4 0 5 2.029 4.410 3 -1 4 1.40...
output:
89.0595921216 71.4725000000 72.3593375998 126.2555698604 53.3211949039 59.8770623446 47.6168767838 66.3827754289 26.7937630789 32.3415000000 139.8534669002 81.6631077387 102.7060531202 81.9198379530 30.2529013266 88.1009981521 102.5549210932 9.0996076136 44.6716546958 46.0261779576 78.3696050285 20....
result:
ok 125 numbers
Test #5:
score: 0
Accepted
time: 4ms
memory: 4232kb
input:
5 -4 -1 4 2.566 3.253 1 -1 2 3.826 4.000 1 2 5 4.113 3.814 -1 -4 2 4.386 3.959 -1 -2 1 5.785 3.937 5 4 2 4 2.417 0.945 -5 -3 3 4.946 5.172 2 -2 2 2.380 0.205 3 3 4 0.766 4.402 -2 4 5 3.442 4.263 5 0 -4 3 5.172 0.603 -4 -5 3 1.321 3.688 -5 1 4 4.363 3.784 -5 -1 4 2.943 2.791 -2 5 3 5.292 5.765 5 -5 -...
output:
79.6935851751 91.7368755682 79.4364704320 77.4532609166 98.2859865867 71.0892243108 7.7255000000 103.2766108978 18.8761113717 83.8517243070 37.1320955728 80.1442018858 100.6075000000 89.2278472871 94.9247284126 24.3560000000 48.9314468494 63.6808639748 99.0233124012 66.8077884000 79.8940642727 114.4...
result:
ok 100 numbers
Test #6:
score: -100
Wrong Answer
time: 9ms
memory: 4308kb
input:
10 4 4 4 2.043 4.661 0 -2 3 4.728 5.010 1 5 5 0.478 2.500 1 2 4 3.314 2.904 4 -4 5 3.408 5.869 -3 1 5 0.644 2.968 2 0 4 5.532 0.421 2 -3 1 3.492 0.855 -3 -3 5 4.475 4.896 -4 -1 3 0.873 1.815 10 -2 -1 3 4.786 3.714 -4 -3 1 0.155 4.804 -1 -5 3 4.225 2.500 -4 -1 4 5.536 3.954 4 -2 4 5.516 2.204 -3 2 4 ...
output:
217.4622557720 137.0804351275 68.2804406589 81.6749055254 161.3947250258 109.8547433732 88.8510980287 149.6638209412 141.2604538005 150.8285832209 103.5306253863 80.0421062943 135.5872223624 124.1546681585 142.2968212704 136.0738797792 149.1473126537 92.2250861713 183.2849698307 153.4337064555 95.69...
result:
wrong answer 24th numbers differ - expected: '162.2110536', found: '162.0052576', error = '0.0012687'