QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#733507 | #9576. Ordainer of Inexorable Judgment | ucup-team5008# | WA | 0ms | 3996kb | C++23 | 4.3kb | 2024-11-10 19:30:12 | 2024-11-10 19:30:13 |
Judging History
你现在查看的是最新测评结果
- [2024-12-23 14:23:26]
- hack成功,自动添加数据
- (/hack/1303)
- [2024-12-06 11:32:56]
- hack成功,自动添加数据
- (/hack/1271)
- [2024-11-14 21:58:28]
- hack成功,自动添加数据
- (/hack/1181)
- [2024-11-10 19:30:12]
- 提交
answer
#include<bits/stdc++.h>
#define rep2(i,j,k) for(ll i = ll(j); i < ll(k); i++)
#define rep(i,k) rep2(i,0,k)
#define rrep2(i,j,k) for(ll i = ll(j)-1; i >= ll(k); i--)
#define rrep(i,k) rrep2(i,k,0)
#define all(a) a.begin(),a.end()
#define SZ(a) ll(a.size())
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
const ll inf = LLONG_MAX/4;
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0;}
bool chmax(auto& a, auto b) {return a < b ? a = b, 1 : 0;}
using ld = long double;
using Point = complex<ld>;
constexpr ld INF = 1e18;
constexpr ld EPS = 1e-6;
bool equal(ld a, ld b) {
return fabsl(a-b) <= EPS;
}
bool equal(Point a, Point b) {
return equal(a.real(), b.real()) && equal(a.imag(), b.imag());
}
Point unitVector(Point a) {
return a / abs(a);
}
Point normalVector(Point a) {
return a * Point(0, 1);
}
ld cross(Point a, Point b) {
return (a.real() * b.imag() - a.imag() * b.real());
}
struct Circle {
Point p;
ld r;
Circle(Point p, ld r) : p(p), r(r) {}
bool contain(Point q) {
return abs(q-p) <= r + EPS;
}
};
int isIntersect(Circle c1, Circle c2) {
ld d = fabs(c1.p-c2.p);
if(d > c1.r + c2.r + EPS) return 4;
if(equal(d, c1.r + c2.r)) return 3;
if(equal(d, fabs(c1.r-c2.r))) return 1;
if(d < fabs(c1.r-c2.r)-EPS) return 0;
return 2;
}
vector<Point> crossPoint(Circle c1, Circle c2) {
vector<Point> res;
int mode = isIntersect(c1, c2);
ld d = abs(c1.p - c2.p);
if(mode == 4 || mode == 0) return res;
if(mode == 3) {
ld t = c1.r / (c1.r + c2.r);
res.eb(c1.p+(c2.p-c1.p)*t);
return res;
}
if(mode == 1) {
if(c2.r < c1.r-EPS) {
res.eb(c1.p + (c2.p-c1.p) * (c1.r / d));
} else {
res.eb(c2.p + (c1.p-c2.p) * (c2.r / d));
}
return res;
}
ld rc1 = (c1.r * c1.r + d * d - c2.r * c2.r) / (2 * d);
ld rs1 = sqrtl(c1.r * c1.r - rc1 * rc1);
if(c1.r - fabs(rc1) < EPS) rs1 = 0;
Point e12 = unitVector(c2.p - c1.p);
res.eb(c1.p + rc1 * e12 + rs1 * normalVector(e12));
res.eb(c1.p + rc1 * e12 - rs1 * normalVector(e12));
return res;
}
vector<Point> tangentToCircle(Point p, Circle c) {
if (c.r > abs(c.p-p)-EPS) return {};
if (equal(c.r, abs(c.p-p))) return {p};
return crossPoint(c, Circle(p, sqrtl(norm(c.p-p)-c.r*c.r)));
}
vector<Point> argSort(vector<Point> p) {
sort(all(p), [](Point a, Point b) {
auto type = [&](Point x) {
if(equal(x, Point(0,0))) return 0;
if(x.imag() > EPS || (equal(x.imag(), 0) && -EPS < x.real())) return -1;
return 1;
};
int ta = type(a), tb = type(b);
if(ta != tb) return ta < tb;
return cross(a, b) > 0;
});
return p;
}
Point input() {
ld x, y; cin >> x >> y;
return Point(x,y);
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
cout << fixed << setprecision(15);
ll n; cin >> n;
Point start = input();
ld d; cin >> d;
ld t; cin >> t;
vector<Point> p(n);
rep(i,n) p[i] = input();
{
rep(i,n){
if(abs(p[i]) < d + EPS){
cout << t << endl;
return 0;
}
}
}
Circle cent(Point(0,0), d);
vector<pair<ld, ll>> data;
rep(i,n){
auto cand = tangentToCircle(p[i], cent);
for(auto el: cand) {
auto cr = p[i]-el;
// cout << p[i] << " " << el << endl;
data.eb(atan2l(cr.imag(), cr.real()), i);
}
}
data.eb(atan2l(start.imag(), start.real())-EPS, -1);
// cout << start << " " << data.back().first << endl;
sort(all(data));
{
vector<pair<ld,ll>> data2;
rep(i,SZ(data)){
if(data[i].second == -1) {
rep2(j,1,SZ(data)){
auto nex = data[(i+j)%SZ(data)];
// cout << nex.first << " ";
if(i+j >= SZ(data)) nex.first += 2 * M_PI;
data2.eb(nex);
}
// cout << endl;
break;
}
}
data = data2;
}
{
ll cnt = 0;
vector<bool> flag(n);
rep(i,n) {
if(p[i].real() > -EPS && abs(p[i].imag()) < d - EPS){
flag[i] = true;
cnt++;
}
}
ll idx = 0;
ld now = atan2l(start.imag(), start.real());
ld goal = now + t;
ld ans = 0;
// for(auto el: data) cout << el.first << " ";
// cout << endl;
while(true) {
ld next = data[idx].first;
// cout << now << " " << next << endl;
ll v = data[idx].second;
if(next >= goal - EPS) {
if(cnt > 0) ans += goal-now;
break;
}
if(cnt > 0) ans += (next-now);
cnt -= flag[v];
flag[v] = !flag[v];
cnt += flag[v];
data[idx].first += 2 * M_PI;
now = next;
idx = (idx+1)%SZ(data);
}
cout << ans << endl;
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3976kb
input:
3 1 0 1 1 1 2 2 1 2 2
output:
1.000000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
3 1 0 1 2 1 2 2 1 2 2
output:
1.570796326794897
result:
ok found '1.5707963', expected '1.5707963', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
3 1 0 1 10000 1 2 2 1 2 2
output:
2500.707752257475330
result:
ok found '2500.7077523', expected '2500.7077523', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3976kb
input:
3 10000 10000 1 10000 10000 9999 10000 10000 9999 10000
output:
9999.934074615240257
result:
wrong answer 1st numbers differ - expected: '0.3842413', found: '9999.9340746', error = '9999.5498333'