QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#734847 | #9576. Ordainer of Inexorable Judgment | Willis | WA | 1ms | 4224kb | C++20 | 10.3kb | 2024-11-11 15:28:47 | 2024-11-11 15:28:48 |
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-11 15:28:47]
- 提交
answer
#ifdef local
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#endif
// #pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#ifndef local
#define endl '\n'
#endif
#define pb emplace_back
#define fi first
#define se second
#define rep(i, l, r) for (long long i = l; i <= r; i++)
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, x) memset(a, x, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double db;
// typedef double db;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;
typedef pair<double, double> PD;
const double pi = acos(-1);
typedef __int128_t int128;
const db eps = 1e-12;
std::mt19937_64 rng(time(0));
ll my_random(ll l, ll r)
{
uniform_int_distribution<int> range(l, r);
return range(rng);
}
void __()
{
#ifdef local
system("pause");
#endif
}
ll qp(ll a, ll b, ll mod)
{
ll ans = 1;
while (b)
{
if (b & 1)
ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
inline int sgn(db x)
{ // 板子有些地方缺sgn, 抄的时候要注意
if (x > eps)
return 1;
if (x < -eps)
return -1;
return 0;
}
struct Point
{
db x, y;
Point() {}
Point(db _x, db _y) : x(_x), y(_y) {}
Point operator+(const Point &t) const
{
return Point(x + t.x, y + t.y);
}
Point operator-(const Point &t) const
{
return Point(x - t.x, y - t.y);
}
Point operator*(const db &t) const
{
return Point(x * t, y * t);
}
Point operator/(const db &t) const
{
return Point(x / t, y / t);
}
db operator*(const Point &t) const
{
// 叉积
return x * t.y - y * t.x;
}
db operator^(const Point &t) const
{
// 点积
return x * t.x + y * t.y;
}
bool operator==(const Point &t) const
{
return sgn(x - t.x) == 0 && sgn(y - t.y) == 0;
}
bool operator!=(const Point &t) const
{
return !((*this) == t);
}
db len() const
{
return sqrt(x * x + y * y);
}
Point norm() const
{
return *this / len();
}
Point rot90() const
{
return Point(-y, x);
}
Point rot(db angle, Point p = Point(0, 0)) const
{
// angle为弧度制
return Point((x - p.x) * cos(angle) - (y - p.y) * sin(angle) + p.x,
(x - p.x) * sin(angle) + (y - p.y) * cos(angle) + p.y);
}
int quadrant() const
{
if (x > 0 && y >= 0)
return 1;
if (x <= 0 && y > 0)
return 2;
if (x < 0 && y <= 0)
return 3;
if (x >= 0 && y < 0)
return 4;
}
};
db dis(Point p, Point q)
{
return sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y));
}
int contain(Point p[], int n, const Point &t)
{
// 判断点是否在凸包中, O(logn), Bailian 1264
// 2在凸包上,1在凸包内,0在凸包外
// 注意p是一个凸包且不包含起始点两次, n为凸包点的个数
Point g = (p[1] + p[n / 3 + 1] + p[2 * n / 3 + 1]) / 3.0;
int l = 1, r = n + 1;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (sgn((p[l] - g) * (p[mid] - g)) > 0)
{
if (sgn((p[l] - g) * (t - g)) >= 0 && sgn((p[mid] - g) * (t - g)) < 0)
r = mid;
else
l = mid;
}
else
{
if (sgn((p[l] - g) * (t - g)) < 0 && sgn((p[mid] - g) * (t - g)) >= 0)
l = mid;
else
r = mid;
}
}
if (r == n + 1)
r = 1;
int z = sgn((p[r] - t) * (p[l] - t));
if (z == -1)
return 1;
if (z == -0)
return 2;
if (z == 1)
return 0;
}
struct Line
{
Point s, e;
db angle; // 记得读入的时候计算angle
Line() {}
Line(Point _s, Point _e) : s(_s), e(_e), angle(atan2(_e.y - _s.y, _e.x - _s.x)) {}
pair<db, Point> disToLine(const Point &t) const
{
// 若点到直线距离则只有下面几行
db k = ((t - s) ^ (e - s)) / ((e - s) ^ (e - s));
return {abs((t - s) * (e - s).norm()), s + (e - s) * k};
}
pair<db, Point> disToSegment(const Point &t) const
{
// 点到线段距离与交点, 距离正确, 交点正确
if (sgn((t - s) ^ (e - s)) < 0)
return {(t - s).len(), s};
if (sgn((t - e) ^ (s - e)) < 0)
return {(t - e).len(), e};
// 若点到直线距离则只有下面几行
db k = ((t - s) ^ (e - s)) / ((e - s) ^ (e - s));
return {abs((t - s) * (e - s).norm()), s + (e - s) * k};
}
};
void angle_sort(vector<Point> &p)
{
// 极角排序, O(nlogn), 统计答案的时候一定要考虑象限和答案的关系, 有的题需要把负y轴下的点翻上来
auto cmp2 = [](Point a, Point b) -> bool { // 依靠象限和叉积排序, 适用整形, 排完序的象限依次为1,2,3,4
if (a.quadrant() == b.quadrant())
return sgn(a * b) == 0 ? a.x < b.x : sgn(a * b) > 0;
return a.quadrant() < b.quadrant();
};
sort(p.begin(), p.end(), cmp2);
}
int n;
Point p[110];
int t;
Point face;
int d;
db calcdis(Point x = Point(0, 0))
{
db Mindis = 1e9;
for (int i = 1; i <= n; i++)
{
Line l = Line(p[i], p[(i + 1 == n + 1) ? 1 : i + 1]);
Mindis = min(Mindis, l.disToSegment(x).fi);
// cout << Mindis << endl;
}
return Mindis;
}
bool check(double theta)
{
Point p1 = Point(cos(theta), sin(theta));
Line l = Line(Point(0, 0), p1);
// cout << p1.x << " " << p1.y << endl;
// cout << endl;
db Mindis = 1e9;
for (int i = 1; i <= n; i++)
{
auto x = l.disToLine(p[i]);
if ((x.se ^ p1) < 0)
continue;
Mindis = min(Mindis, x.fi);
}
return sgn(d - Mindis) >= 0;
}
int main()
{
IOS;
// cout << atan2(1, 0) << " " << atan2(-1, 0) << " " << atan2(-1, 1) << " " << atan2(1, -1) << " " << atan2(0, 1) << " " << atan2(0, -1) << endl;
cin >> n;
cin >> face.x >> face.y;
cin >> d >> t;
Point center = Point();
for (int i = 1; i <= n; i++)
{
cin >> p[i].x >> p[i].y;
center = center + p[i] / n;
}
// cout << calcdis() << endl;
if (contain(p, n, Point(0, 0)) || sgn(1.0 * d - calcdis()) >= 0)
{
// cout << "XXX " << endl;
cout << t << endl;
__();
return 0;
}
set<int> st;
vector<Point> vec[5];
for (int i = 1; i <= n; i++)
{
st.insert(p[i].quadrant());
vec[p[i].quadrant()].pb(p[i]);
}
Point l, r;
bool cross = false;
if (st.size() == 1)
{
int q = p[1].quadrant();
angle_sort(vec[q]);
l = vec[q][0];
r = vec[q][vec[q].size() - 1];
}
else if (st.size() == 2)
{
int quad1 = *st.begin();
int quad2 = *(--st.end());
angle_sort(vec[quad1]);
angle_sort(vec[quad2]);
if (quad1 == 1 && quad2 == 4)
{
r = vec[quad1][vec[quad1].size() - 1];
l = vec[quad2][0];
cross = true;
// for(auto x:vec[quad2])
// {
// cout << x.x << " " << x.y << " " << atan2(x.y , x.x) << endl;
// }
}
else
{
l = vec[quad1][0];
r = vec[quad2][vec[quad2].size() - 1];
}
}
else
{
int disa = 0;
for (int i = 1; i <= 4; i++)
if (st.find(i) == st.end())
{
disa = i;
break;
}
assert(disa != 0);
if (disa == 1 || disa == 4)
{
int quad1 = *st.begin();
int quad2 = *(--st.end());
// cout << "XX " << quad1 << " " << quad2 << endl;
angle_sort(vec[quad1]);
angle_sort(vec[quad2]);
// for(auto x:vec[quad2])
// {
// cout << x.x << " " << x.y << " " << atan2(x.y , x.x) << endl;
// }
l = vec[quad1][0];
r = vec[quad2][vec[quad2].size() - 1];
}
else if (disa == 2)
{
int quad1 = 3;
int quad2 = 1;
angle_sort(vec[quad1]);
angle_sort(vec[quad2]);
l = vec[quad1][0];
r = vec[quad2][vec[quad2].size() - 1];
cross = true;
}
else
{
int quad1 = 4;
int quad2 = 2;
angle_sort(vec[quad1]);
angle_sort(vec[quad2]);
l = vec[quad1][0];
r = vec[quad2][vec[quad2].size() - 1];
cross = true;
}
}
// cout << "XXX " << l.x << " " << l.y << " XXX " << r.x << " " << r.y << endl;
l = l / l.len();
r = r / r.len();
Point mid = (l + r) / 2;
mid = mid * -1;
double thetal = atan2(l.y, l.x), thetar = atan2(r.y, r.x), thetamid = atan2(mid.y, mid.x);
//cout << fixed << setprecision(15) << "XX theta " << thetal << " " << thetar << " " << endl;
check(thetal);
check(thetar + 2 * pi);
if (sgn(thetal) < 0)
thetal += 2 * pi;
if (sgn(thetar) < 0)
thetar += 2 * pi;
if (sgn(thetamid) < 0)
thetamid += 2 * pi;
double l1 = thetamid, r1 = thetal;
double l2 = thetar, r2 = thetamid;
if (l1 > r1)
l1 -= 2 * pi;
if (l2 > r2)
r2 += 2 * pi;
double mid1, mid2;
//cout << fixed << setprecision(15) << "l r " << l1 << " " << r1 << " XXX " << l2 << " " << r2 << endl;
for (int i = 1; i <= 100; i++)
{
mid1 = (l1 + r1) / 2;
mid2 = (l2 + r2) / 2;
if (check(mid1)) // true <= d, false > d
r1 = mid1;
else
l1 = mid1;
if (check(mid2)) // true <= d, false > d
l2 = mid2;
else
r2 = mid2;
}
if (sgn(mid1) < 0)
mid1 += 2 * pi;
if (sgn(mid2) < 0)
mid2 += 2 * pi;
//cout << fixed << setprecision(15) << mid1 << " " << mid2 << endl;
vector<pair<double, double>> inter;
if (cross == false)
{
if (mid1 <= 0)
inter.pb(PD(0, mid2)), inter.pb(PD(2 * pi - mid1, 2 * pi));
else if (mid2 >= 2 * pi)
inter.pb(PD(0, 2 * pi - mid2)), inter.pb(PD(mid1, 2 * pi));
else
inter.pb(PD(mid1, mid2));
}
else
inter.pb(PD(0, thetar)), inter.pb(PD(mid1, 2 * pi));
int cycles = 1.0 * t / (2 * pi);
double remain = 1.0 * t - cycles * 2 * pi;
double all_len = 0;
for (auto x : inter)
all_len += x.se - x.fi;
double ans = all_len * cycles;
//cout << "XX " << fixed << setprecision(15) << ans << endl;
double theta_begin = atan2(face.y, face.x);
if (sgn(theta_begin) < 0)
theta_begin += 2 * pi;
vector<pair<double, double>> inter2 = inter;
for (int i = 0; i < inter.size(); i++)
inter2.pb(PD(inter[i].fi + 2 * pi, inter[i].se + 2 * pi));
for (int i = 0; i < inter.size(); i++)
inter2.pb(PD(inter[i].fi + 4 * pi, inter[i].se + 4 * pi));
for (auto &x : inter2)
{
x.fi -= theta_begin, x.se -= theta_begin;
}
for (auto x : inter2)
{
if (remain > x.fi)
ans += min(remain, x.se) - max(x.fi, 0.0);
}
cout << fixed << setprecision(15) << ans << endl;
__();
return 0;
}
/*
5 1 0 1 10
-9 4
-10 4
-10 -10
4 -10
4 -9
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4128kb
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: 4068kb
input:
3 1 0 1 2 1 2 2 1 2 2
output:
1.570796326795397
result:
ok found '1.5707963', expected '1.5707963', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
3 1 0 1 10000 1 2 2 1 2 2
output:
2500.707752257475931
result:
ok found '2500.7077523', expected '2500.7077523', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4216kb
input:
3 10000 10000 1 10000 10000 9999 10000 10000 9999 10000
output:
0.384241300290388
result:
ok found '0.3842413', expected '0.3842413', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4224kb
input:
3 -10000 -10000 10000 10000 -10000 -9999 -10000 -10000 -9999 -10000
output:
2500.240670009608493
result:
ok found '2500.2406700', expected '2500.2406700', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4152kb
input:
4 1 0 1 10000 -2 3400 -4 10000 -4 -10000 -2 -3400
output:
4999.219115408744074
result:
ok found '4999.2191154', expected '4999.2191154', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
4 1 0 1 10000 -2 3300 -4 10000 -4 -10000 -2 -3300
output:
4999.200391854817099
result:
ok found '4999.2003919', expected '4999.2003919', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4196kb
input:
4 -3040 2716 2147 2 -9033 -8520 -8999 -8533 -8988 -8511 -9004 -8495
output:
0.350830058342073
result:
ok found '0.3508301', expected '0.3508301', error '0.0000000'
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 4224kb
input:
3 8168 -766 1549 1256 -3951 -6425 -3874 -6439 -3911 -6389
output:
83.021564504336339
result:
wrong answer 1st numbers differ - expected: '84.8328612', found: '83.0215645', error = '0.0213514'