QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662485 | #7310. Circular Sectors | AnKozhevnikov | WA | 1952ms | 4320kb | C++23 | 9.0kb | 2024-10-21 01:28:44 | 2024-10-21 01:28:46 |
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 p1 = sec.y + sqrt(fsqr(sec.r) - fsqr(sec.x - x));
if (sec.inside(x, p1))
ys.push_back(p1);
double p2 = sec.y - sqrt(fsqr(sec.r) - fsqr(sec.x - x));
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 (int 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 (int 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)
{
s.insert(p);
auto it = s.find(p);
auto itprev = it;
while (it != s.begin() && joint(*(--itprev), *it))
{
pair<double, double> np = merge(*it, *itprev);
s.erase(it);
s.erase(itprev);
p = np;
s.insert(p);
it = s.find(p);
itprev = it;
}
auto itnext = it;
++itnext;
while (itnext != s.end() && joint(*itnext, *it))
{
pair<double, double> np = merge(*it, *itnext);
s.erase(it);
s.erase(itnext);
p = np;
s.insert(p);
it = s.find(p);
itnext = it;
++itnext;
}
}
class Event
{
public:
double x;
int num;
bool open;
Event(double x, int num, bool open)
{
this->x = x;
this->num = num;
this->open = open;
}
bool operator<(Event &other) const
{
return x < other.x;
}
};
void task(int n)
{
vector<Sector> v(n);
vector<Event> events;
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((double)v[i].x - v[i].r, (int)i, true));
events.push_back(Event((double)v[i].x + v[i].r, (int)i, false));
}
sort(events.begin(), events.end());
unordered_set<int> opened;
int cur = 0;
double totallen=0;
double lastx = events[0].x;
int balance=1;
for (int i=1; i<events.size(); ++i) {
if (events[i].open) {
++balance;
if (balance==1) {
lastx = events[i].x;
}
}
else {
--balance;
if (balance==0) {
totallen+=events[i].x-lastx;
}
}
}
double ans = 0;
double step = totallen*totallen/22e4;
for (double i = events[0].x; i < events.back().x; i += step)
{
while (cur != events.size() && events[cur].x <= i)
{
if (events[cur].open)
opened.insert(events[cur].num);
else
opened.erase(events[cur].num);
++cur;
}
if (opened.size() == 0)
{
if (cur == events.size())
break;
i = events[cur].x;
i -= step;
continue;
}
set<pair<double, double>> s;
for (auto ind : opened)
{
vector<pair<double, double>> ns = getPts(i, v[ind]);
for (auto it : ns)
{
insert(s, it);
}
}
double calc = 0;
for (auto it : s)
{
calc += it.second - it.first;
}
ans += calc * step;
}
cout << 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();*/
int n;
while (cin >> n)
{
task(n);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 38ms
memory: 4284kb
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.800490045216684 1.129999999949994 106.444942658976444
result:
ok 3 numbers
Test #2:
score: -100
Wrong Answer
time: 1952ms
memory: 4320kb
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.937500011043304 45.712530849952749 43.533917001866186 31.801995377777853 41.885977784750132 12.931995869184034 31.713090696903492 9.889986318389536 3.811498891461254 26.789990155059691 37.187487407703628 10.700499586877989 31.423495843806528 47.663994111543026 25.456499935401208 54.013580026764735...
result:
wrong answer 8th numbers differ - expected: '9.8900000', found: '9.8899863', error = '0.0000014'