QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662536 | #7310. Circular Sectors | AnKozhevnikov | TL | 1964ms | 4524kb | C++23 | 12.1kb | 2024-10-21 02:27:00 | 2024-10-21 02:27:00 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl
// #define int long long
// #pragma comment(linker, "/STACK:200000000")
// #pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")
const long long mod = 1e9 + 7;
// const long long mod = 998244353;
// const long long mod = 786433;
const long double eps = 1e-9;
const long double pi = acosl(-1.0);
mt19937_64 engine;
mt19937 engine32;
inline long long sqr(long long x)
{
return x * x;
}
inline double fsqr(double x)
{
return x * x;
}
long long binpow(long long x, long long y)
{
if (y == 0)
return 1;
if (y == 1)
return x;
long long f = binpow(x, y / 2);
if (y % 2 == 0)
return (f * f) % mod;
else
return (((f * f) % mod) * x) % mod;
}
long long gcd(long long x, long long y)
{
if (x == 0)
return y;
else
return gcd(y % x, x);
}
long long lcm(long long x, long long y)
{
return x / gcd(x, y) * y;
}
struct Vector
{
long double x, y;
Vector operator+(Vector v1) const
{
return {x + v1.x, y + v1.y};
}
Vector operator-(Vector v1) const
{
return {x - v1.x, y - v1.y};
}
Vector operator*(long double l) const
{
return {x * l, y * l};
}
Vector operator/(long double l) const
{
return {x / l, y / l};
}
bool operator==(Vector v1)
{
if (abs(x - v1.x) <= eps && abs(y - v1.y) <= eps)
{
return true;
}
else
{
return false;
}
}
bool operator!=(Vector v1)
{
if (abs(x - v1.x) > eps || abs(y - v1.y) > eps)
{
return true;
}
else
{
return false;
}
}
long double len()
{
return sqrt(x * x + y * y);
}
void norm()
{
long double l = len();
x /= len();
y /= len();
}
void set(long double f)
{
norm();
x *= f;
y *= f;
}
};
struct Line
{
long double a, b, c;
};
#define Point Vector
long double dot(Vector v1, Vector v2)
{
return v1.x * v2.x + v1.y * v2.y;
}
long double cross(Vector v1, Vector v2)
{
return v1.x * v2.y - v1.y * v2.x;
}
Vector make_vector(Point p1, Point p2)
{
return {p2.x - p1.x, p2.y - p1.y};
}
Line make_line(Point p1, Point p2)
{
long double a = p1.y - p2.y;
long double b = p2.x - p1.x;
long double c = -b * p1.y - a * p1.x;
Vector v = {a, b};
long double dist = v.len();
return {a / dist, b / dist, c / dist};
}
Point intersec(Line l1, Line l2)
{
if (l1.a * l2.b - l2.a * l1.b == 0 || l1.a * l2.b - l2.a * l1.b == 0)
{
return {(long double)LLONG_MAX, (long double)LLONG_MAX};
}
else
{
return {-(l1.c * l2.b - l2.c * l1.b) / (l1.a * l2.b - l2.a * l1.b),
-(l2.c * l1.a - l1.c * l2.a) / (l1.a * l2.b - l2.a * l1.b)};
}
}
class Sector
{
public:
int x, y, r;
double s, a;
bool inside(double x, double y)
{
if (fabs(x - this->x) < eps && fabs(y - this->y) < eps)
return true;
double l = s;
double r = s + a;
double angle = atan2(y - this->y, x - this->x);
if (angle < l)
angle += 2 * pi;
if (angle < l)
angle += 2 * pi;
double rad = sqrt(fsqr(this->x - x) + fsqr(this->y - y));
return rad - eps < this->r && angle + eps >= l && angle - eps <= r;
}
};
bool onSegment(Point p, Point p1, Point p2)
{
return ((p.x >= p1.x && p.x <= p2.x) || (p.x <= p1.x && p.x >= p2.x)) &&
((p.y >= p1.y && p.y <= p2.y) || (p.y <= p1.y && p.y >= p2.y));
}
inline vector<pair<double, double>> getPts(double x, Sector sec)
{
if (fabs(x - sec.x) >= 100)
return {};
vector<double> ys;
double rr = sec.r * sec.r;
double dx2 = (sec.x - x) * (sec.x - x);
double sqrt_val = sqrt(rr - dx2);
double p1 = sec.y + sqrt_val;
if (sec.inside(x, p1))
ys.push_back(p1);
double p2 = sec.y - sqrt_val;
if (sec.inside(x, p2))
ys.push_back(p2);
if (fabs(x - sec.x) < eps)
{
if (ys.size() == 1)
{
ys.push_back(sec.y);
}
sort(ys.begin(), ys.end());
vector<pair<double, double>> ret;
for (size_t i = 0; i < ys.size(); i += 2)
{
ret.push_back({ys[i], ys[i + 1]});
}
return ret;
}
Point r1 = {sec.r * cos(sec.s) + sec.x, sec.r * sin(sec.s) + sec.y};
Point r2 = {sec.r * cos(sec.s + sec.a) + sec.x, sec.r * sin(sec.s + sec.a) + sec.y};
Point mid = {sec.x, sec.y};
Line l1 = make_line(mid, r1);
Line l2 = make_line(mid, r2);
Line l3 = make_line({x, 0}, {x, 1});
Point intersec1 = intersec(l1, l3);
Point intersec2 = intersec(l2, l3);
if (onSegment(intersec1, mid, r1))
ys.push_back(intersec1.y);
if (onSegment(intersec2, mid, r2))
ys.push_back(intersec2.y);
sort(ys.begin(), ys.end());
vector<pair<double, double>> ret;
for (size_t i = 0; i < ys.size(); i += 2)
{
ret.push_back({ys[i], ys[i + 1]});
}
return ret;
}
inline bool joint(pair<double, double> s1, pair<double, double> s2)
{
return !(s1.first > s2.second || s1.second < s2.first);
}
inline pair<double, double> merge(pair<double, double> s1, pair<double, double> s2)
{
return {min(s1.first, s2.first), max(s1.second, s2.second)};
}
void insert(set<pair<double, double>> &s, pair<double, double> p)
{
auto it = s.lower_bound(p);
if (it != s.begin() && joint(*prev(it), p))
{
--it;
}
while (it != s.end() && joint(*it, p))
{
p = merge(p, *it);
it = s.erase(it);
}
s.insert(p);
}
class Event
{
public:
int qnum;
double x;
int num;
bool open;
Event(int qnum, double x, int num, bool open)
{
this->qnum = qnum;
this->x = x;
this->num = num;
this->open = open;
}
bool operator<(Event &other) const
{
return x < other.x;
}
};
class Q
{
public:
int n;
vector<Sector> v;
double ans;
double s;
Q(int on, vector<Sector> ov, double oans, double os) : n(on), v(ov), ans(oans), s(os)
{
}
};
void task()
{
vector<Q> qs;
int n;
while (cin >> n)
{
qs.push_back(Q(n, vector<Sector>(), 0, 0));
vector<Sector> v(n);
for (int i = 0; i < n; ++i)
{
cin >> v[i].x >> v[i].y >> v[i].r >> v[i].s >> v[i].a;
// events.push_back(Event((int)qs.size() - 1, (double)v[i].x - v[i].r, (int)i, true));
// events.push_back(Event((int)qs.size() - 1, (double)v[i].x + v[i].r, (int)i, false));
qs.back().s += v[i].r * v[i].r * v[i].a / 2;
}
qs.back().v = v;
}
vector<Event> eventsBig;
vector<Event> eventsSmall;
for (int i = 0; i < qs.size(); ++i)
{
if (qs[i].s > 15)
{
for (int j = 0; j < qs[i].n; ++j)
{
eventsBig.push_back(Event(i, (double)qs[i].v[j].x - qs[i].v[j].r, j, true));
eventsBig.push_back(Event(i, (double)qs[i].v[j].x + qs[i].v[j].r, j, false));
}
}
else
{
for (int j = 0; j < qs[i].n; ++j)
{
eventsSmall.push_back(Event(i, (double)qs[i].v[j].x - qs[i].v[j].r, j, true));
eventsSmall.push_back(Event(i, (double)qs[i].v[j].x + qs[i].v[j].r, j, false));
}
}
}
sort(eventsBig.begin(), eventsBig.end());
int cur = 0;
vector<unordered_set<int>> opened(qs.size());
int balance = 0;
double step = 3871e-7;
if (!eventsBig.empty())
{
for (double i = eventsBig[0].x; i < eventsBig.back().x; i += step)
{
while (cur != eventsBig.size() && eventsBig[cur].x <= i)
{
if (eventsBig[cur].open)
{
if (opened[eventsBig[cur].qnum].empty())
++balance;
opened[eventsBig[cur].qnum].insert(eventsBig[cur].num);
}
else
{
opened[eventsBig[cur].qnum].erase(eventsBig[cur].num);
if (opened[eventsBig[cur].qnum].empty())
--balance;
}
++cur;
}
if (balance == 0)
{
if (cur == eventsBig.size())
break;
i = eventsBig[cur].x;
i -= step;
continue;
}
for (int j = 0; j < qs.size(); ++j)
{
if (opened[j].empty())
continue;
set<pair<double, double>> segs;
for (auto sect : opened[j])
{
vector<pair<double, double>> ns = getPts(i, qs[j].v[sect]);
for (auto it : ns)
{
insert(segs, it);
}
}
double calc = 0;
for (auto it : segs)
{
calc += (it.second - it.first) * step;
}
qs[j].ans += calc;
}
}
}
step = 22e-5;
sort(eventsSmall.begin(), eventsSmall.end());
cur = 0;
opened.clear();
opened.resize(qs.size());
balance = 0;
if (!eventsSmall.empty())
{
for (double i = eventsSmall[0].x; i < eventsSmall.back().x; i += step)
{
while (cur != eventsSmall.size() && eventsSmall[cur].x <= i)
{
if (eventsSmall[cur].open)
{
if (opened[eventsSmall[cur].qnum].empty())
++balance;
opened[eventsSmall[cur].qnum].insert(eventsSmall[cur].num);
}
else
{
opened[eventsSmall[cur].qnum].erase(eventsSmall[cur].num);
if (opened[eventsSmall[cur].qnum].empty())
--balance;
}
++cur;
}
if (balance == 0)
{
if (cur == eventsSmall.size())
break;
i = eventsSmall[cur].x;
i -= step;
continue;
}
for (int j = 0; j < qs.size(); ++j)
{
if (opened[j].empty())
continue;
set<pair<double, double>> segs;
for (auto sect : opened[j])
{
vector<pair<double, double>> ns = getPts(i, qs[j].v[sect]);
for (auto it : ns)
{
insert(segs, it);
}
}
double calc = 0;
for (auto it : segs)
{
calc += (it.second - it.first) * step;
}
qs[j].ans += calc;
}
}
}
for (int i = 0; i < qs.size(); ++i)
{
cout << qs[i].ans << endl;
}
}
signed main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// engine.seed(1);
engine.seed(58);
// engine.seed(time(0));
engine32.seed(58);
cout << fixed << setprecision(15);
bool multitest = 0;
int t = 1;
if (multitest)
cin >> t;
while (t--)
task();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 26ms
memory: 4344kb
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.800493648699323 1.129999999853039 106.444938037253380
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 1964ms
memory: 4500kb
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.937499996668222 45.712500861066474 43.533916437599643 31.802005299338436 41.886004562367766 12.931998139482154 31.713098249981012 9.890000334828095 3.811501829942192 26.789996348704022 37.187490393222070 10.700501578771256 31.423501076830185 47.663998223049681 25.456502262311986 54.013595023801699...
result:
ok 250 numbers
Test #3:
score: 0
Accepted
time: 1828ms
memory: 4404kb
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.157872556564939 33.234993984789327 47.749462246370591 82.280003970619561 38.565000121966662 57.287501958397087 16.887501363868044 30.812464320004118 18.266139038751966 43.264626345376499 42.494224815289833 26.132747159914544 26.404499239526025 30.106732361450131 48.936997560737389 23.139495667018...
result:
ok 166 numbers
Test #4:
score: 0
Accepted
time: 1813ms
memory: 4524kb
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.059588710158394 71.472507252297916 72.359331417524075 126.255572409465955 53.321194331822163 59.877064469981960 47.616875824805582 66.382780012456692 26.793766498371614 32.341504610708768 139.853465133715588 81.663102849077816 102.706055738124633 81.919838103859462 30.252892753345609 88.101002347...
result:
ok 125 numbers
Test #5:
score: 0
Accepted
time: 1662ms
memory: 4388kb
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.693582239334077 91.736881246842103 79.436470640508460 77.453235871714085 98.285983681175608 71.089216970334988 7.725498403134583 103.276613145004944 18.876110626753857 83.851723310187722 37.132095376387312 80.144202170853561 100.607512086478422 89.227845251574834 94.924727000219860 24.35599455869...
result:
ok 100 numbers
Test #6:
score: 0
Accepted
time: 1753ms
memory: 4440kb
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.462253484813800 137.080447667723291 68.280433711378393 81.674906576563203 161.394724651012410 109.854746382097389 88.851102384195883 149.663826040380712 141.260468682797523 150.828567255340261 103.530634687476550 80.042106054795880 135.587218921943673 124.154675168170087 142.296820344155719 136....
result:
ok 50 numbers
Test #7:
score: -100
Time Limit Exceeded
input:
9 6 -5 6 4.848 5.374 9 4 3 2.135 4.598 8 -4 6 4.443 5.157 0 5 9 3.605 1.226 7 -4 9 1.917 4.657 6 -7 8 3.621 0.258 3 3 4 1.955 5.563 -6 -5 5 3.174 3.778 -10 9 1 5.808 1.214 10 2 0 8 5.479 1.980 -3 -1 10 2.909 0.574 -8 -10 4 1.758 4.039 2 -6 9 5.761 4.499 1 1 2 0.115 0.897 -3 7 6 0.574 4.703 -4 5 6 0....