QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300055 | #7310. Circular Sectors | mshcherba | RE | 3ms | 4236kb | C++20 | 7.8kb | 2024-01-07 17:01:28 | 2024-01-07 17:01:29 |
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 pair<int, int> PII;
typedef double db;
const db EPS = 1e-9;
const db PI = acos(-1.0);
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);
}
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;
}
db cross(const Pt& p, const Pt& q)
{
return p.x * q.y - p.y * q.x;
}
db orient(const Pt& p, const Pt& q, const Pt& r)
{
return cross(q - p, r - p) / abs(q - p);
}
ostream& operator<<(ostream& os, const Pt& p)
{
return os << "(" << p.x << "," << p.y << ")";
}
struct Line
{
Pt n;
db c;
Line(const Pt& p, const Pt& q):
n(perp(q - p)), c(-dot(n, p)) {}
db side(const Pt& p) const
{
return dot(n, p) + c;
}
db sqDist(const Pt& p) const
{
return side(p) * side(p) / (db)sq(n);
}
Pt proj(const Pt& p) const
{
return p - n * 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;
}
bool inDisk(const Pt& a, const Pt& b,
const Pt& p)
{
return sgn(dot(a - p, b - p)) <= 0;
}
bool onSegment(const Pt& a, const Pt& b,
const Pt& p)
{
return sgn(orient(a, b, p)) == 0
&& inDisk(a, b, p);
}
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};
}
vector<Pt> circleCircle(const Pt& o1, db r1,
const Pt& o2, db r2)
{
Pt d = o2 - o1;
db d2 = sq(d);
if (sgn(d2) == 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};
}
bool strictlyIncreasing(db a, db b, db c)
{
return sgn(a - b) < 0 && sgn(b - c) < 0;
}
struct Sector
{
Pt o;
db r, s, theta;
Pt p1, p2;
};
vector<Sector> sectors;
vector<Line> lines;
struct Event
{
db x;
int i, j, k;
bool operator<(const Event& event) const
{
return sgn(x - event.x) < 0;
}
};
db getY(const PII& ij, db x)
{
const auto& [i, j] = ij;
if (j == 0)
{
const Line& l = lines[i];
return -(l.n.x * x + l.c) / l.n.y;
}
const Pt& o = sectors[i].o;
db r = sectors[i].r;
return o.y + j * sqrt(max(0.0, r * r - (x - o.x) * (x - o.x)));
};
struct Comparator
{
static db x;
bool operator() (const PII& a, const PII& b) const
{
return sgn(getY(a, x) - getY(b, x)) < 0;
}
};
db Comparator::x;
db getAreaOfCirclePart(db r, db x)
{
db co = clamp(x / r, -1.0, 1.0);
db alpha = acos(co);
return (PI - alpha + co * sqrt(1 - co * co)) * r * r / 2;
}
void solve(int n)
{
sectors.resize(n);
lines.clear();
VI linesBalances;
for (auto& [o, r, s, theta, p1, p2] : sectors)
{
cin >> o.x >> o.y >> r >> s >> theta;
p1 = {o.x + r * cos(s), o.y + r * sin(s)};
linesBalances.PB(sgn(cos(s)));
p2 = {o.x + r * cos(s + theta), o.y + r * sin(s + theta)};
linesBalances.PB(-sgn(cos(s + theta)));
lines.PB({o, p1});
lines.PB({o, p2});
}
vector<Event> events;
FOR(i, 0, n)
{
const auto& [o, r, s, theta, p1, p2] = sectors[i];
if (strictlyIncreasing(s, PI, s + theta)
|| strictlyIncreasing(s, 3 * PI, s + theta))
{
events.PB({o.x - r, i, -1, 1});
events.PB({o.x - r, i, 1, 1});
}
if (strictlyIncreasing(s, 2 * PI, s + theta))
{
events.PB({o.x + r, i, -1, -1});
events.PB({o.x + r, i, 1, -1});
}
if (sgn(p1.y - o.y) > 0
|| (sgn(p1.y - o.y) == 0 && sgn(p1.x - o.x) > 0))
{
events.PB({p1.x, i, 1, -1});
}
else
{
events.PB({p1.x, i, -1, 1});
}
if (sgn(p2.y - o.y) > 0
|| (sgn(p2.y - o.y) == 0 && sgn(p2.x - o.x) < 0))
{
events.PB({p2.x, i, 1, 1});
}
else
{
events.PB({p2.x, i, -1, -1});
}
int idxLine = 2 * i;
for (const Pt& p : {p1, p2})
{
assert(sgn(p.x - o.x) != 0);
bool toLeft = sgn(o.x - p.x) < 0;
events.PB({o.x, idxLine, 0, toLeft ? 1 : -1});
events.PB({p.x, idxLine, 0, toLeft ? -1 : 1});
idxLine++;
}
FOR(j, 0, n)
{
if (j == i)
continue;
const auto& sector = sectors[j];
if (j < i)
{
vector<Pt> cc = circleCircle(o, r, sector.o, sector.r);
for (const Pt& q : cc)
{
// redundant events
for (int idx : {i, j})
for (int lu : {-1, 1})
events.PB({q.x, idx, lu, 0});
}
}
idxLine = 2 * j;
for (const Pt& p : {sector.p1, sector.p2})
{
vector<Pt> cl = circleLine(o, r, lines[idxLine]);
for (const Pt& q : cl)
{
if (onSegment(sector.o, p, q))
{
for (int lu : {-1, 1})
events.PB({q.x, i, lu, 0});
events.PB({q.x, idxLine, 0, 0});
}
}
idxLine++;
}
}
}
FOR(i, 0, 2 * n)
{
Pt o1 = sectors[i / 2].o;
Pt pi = i % 2 == 0 ? sectors[i / 2].p1 : sectors[i / 2].p2;
FOR(j, 0, i)
{
if (i / 2 == j / 2 || parallel(lines[i], lines[j]))
continue;
Pt o2 = sectors[j / 2].o;
Pt pj = j % 2 == 0 ? sectors[j / 2].p1 : sectors[j / 2].p2;
Pt q = inter(lines[i], lines[j]);
if (onSegment(o1, pi, q)
&& onSegment(o2, pj, q))
{
events.PB({q.x, i, 0, 0});
events.PB({q.x, j, 0, 0});
}
}
}
set<PII, Comparator> curves;
sort(ALL(events));
db ans = 0;
for(int idxEvent = 0; ;)
{
set<PII> del, add, delAdd;
int ptr = idxEvent;
while (ptr < SZ(events) && !(events[idxEvent] < events[ptr]))
{
//cerr << "event " << events[ptr].x << " " << events[ptr].i << " " << events[ptr].j << " " << events[ptr].k << endl;
PII cur = {events[ptr].i, events[ptr].j};
if (events[ptr].k == -1)
del.insert(cur);
else if (events[ptr].k == 1)
add.insert(cur);
else
delAdd.insert(cur);
ptr++;
}
for (const PII& ij : del)
{
curves.erase(ij);
}
for (const PII& ij : delAdd)
{
if (del.count(ij) || add.count(ij) || !curves.count(ij))
continue;
curves.erase(ij);
add.insert(ij);
}
if (ptr == SZ(events))
break;
db xl = events[idxEvent].x, xr = events[ptr].x;
Comparator::x = (xl + xr) / 2;
for (const PII& ij : add)
{
curves.insert(ij);
}
int bal = 0;
for (const PII& ij : curves)
{
const auto& [i, j] = ij;
int deltaBal = j == 0 ? linesBalances[i] : -j;
assert(bal >= 0);
if (bal == 0 || bal + deltaBal == 0)
{
db area;
if (j == 0)
{
area = (getY(ij, xl) + getY(ij, xr)) * (xr - xl) / 2;
}
else
{
const Pt& o = sectors[i].o;
db r = sectors[i].r;
area = j * (getAreaOfCirclePart(r, xr - o.x) - getAreaOfCirclePart(r, xl - o.x)) + o.y * (xr - xl);
}
ans -= deltaBal * area;
}
bal += deltaBal;
}
assert(bal == 0);
idxEvent = ptr;
}
cout << ans << "\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
int n;
while (cin >> n)
{
solve(n);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4224kb
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.800499999999985 1.129999999999999 106.444931438703563
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 4152kb
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.937500000000004 45.712499999999999 43.533920893527551 31.802000000000007 41.886000000000010 12.932000000000000 31.713102368390359 9.889999999999997 3.811499999999999 26.789999999999999 37.187500000000007 10.700500000000000 31.423499999999983 47.664000000000001 25.456499999999998 54.013595092918770...
result:
ok 250 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 4236kb
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.157879726552892 33.234999999999999 47.749461461744588 82.280000000000015 38.564999999999998 57.287499999999994 16.887499999999999 30.812466324073270 18.266137364384576 43.264634755237466 42.494217510621972 26.132749175803266 26.404499999999981 30.106728114671803 48.936999999999998 23.139499999999...
result:
ok 166 numbers
Test #4:
score: -100
Runtime Error
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...