QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662526 | #7310. Circular Sectors | AnKozhevnikov | TL | 28ms | 4384kb | C++23 | 12.1kb | 2024-10-21 02:19:11 | 2024-10-21 02:19:11 |
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 = 38e-5;
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: 28ms
memory: 4384kb
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.800491924843627 1.129999999853039 106.444929573757406
result:
ok 3 numbers
Test #2:
score: -100
Time Limit Exceeded
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.712503800127443 43.533927890210180 31.802004080840881 41.885999792425075 12.931998139482154 31.713094686302341 9.890000334828095 3.811501829942192 26.790001447332486 37.187504352491047 10.700501578771256 31.423499031541517 47.663993004958130 25.456500452150625 54.013598919557097...