QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662531 | #7310. Circular Sectors | AnKozhevnikov | WA | 1993ms | 4396kb | C++23 | 12.1kb | 2024-10-21 02:22:55 | 2024-10-21 02:22:55 |
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 = 388e-6;
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: 27ms
memory: 4248kb
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.800492743124451 1.129999999853039 106.444935679099785
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 1993ms
memory: 4396kb
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.712497700433843 43.533915365169520 31.802003737677154 41.886000387749426 12.931998139482154 31.713096891710190 9.890000334828095 3.811501829942192 26.789997746799237 37.187502057362387 10.700501578771256 31.423501040851473 47.663995878868263 25.456501487255906 54.013593615043618...
result:
ok 250 numbers
Test #3:
score: 0
Accepted
time: 1783ms
memory: 4388kb
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.157882568700899 33.235005809768744 47.749461546545767 82.279999563858794 38.565000918991736 57.287501749502091 16.887500579942245 30.812467011602305 18.266139069844105 43.264629943458687 42.494222094832459 26.132747296053680 26.404499397843562 30.106728917176763 48.937000953544519 23.139500734641...
result:
ok 166 numbers
Test #4:
score: 0
Accepted
time: 1838ms
memory: 4332kb
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.059598220020362 71.472504333802036 72.359334364140508 126.255570000899326 53.321192932996979 59.877065335249036 47.616876319309974 66.382775305408998 26.793766694091282 32.341505704758482 139.853462205563517 81.663113646816342 102.706053394586505 81.919838641570081 30.252902226319339 88.101002458...
result:
ok 125 numbers
Test #5:
score: 0
Accepted
time: 1673ms
memory: 4356kb
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.693593671354236 91.736880528556838 79.436466868315151 77.453234227346030 98.285987989169683 71.089223565364009 7.725498403134583 103.276614094267018 18.876109226989382 83.851720634312500 37.132092699092013 80.144207328539196 100.607511575116405 89.227854847056463 94.924724694004752 24.35599738385...
result:
ok 100 numbers
Test #6:
score: -100
Wrong Answer
time: 1764ms
memory: 4392kb
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.462258355667359 137.080442928706987 68.280436751003904 81.674910986804093 161.394731759442152 109.854750868063476 88.851102311859506 149.663823145996218 141.260463953018558 150.828564634230901 103.530633829435914 80.042102137270007 135.587236795485182 124.154670375369435 142.296824853934396 136....
result:
wrong answer 36th numbers differ - expected: '46.3949066', found: '46.3949782', error = '0.0000015'