QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#734870#9576. Ordainer of Inexorable JudgmentWillisWA 0ms4288kbC++2010.1kb2024-11-11 15:35:582024-11-11 15:36:01

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:36:01]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4288kb
  • [2024-11-11 15:35:58]
  • 提交

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;
		}
		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, mid2)), 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 (auto &x : inter2)
		x.fi -= theta_begin, x.se -= theta_begin;
	for (auto x : inter2)
	{
		if (remain > x.fi)
			ans += max(min(remain, x.se) - max(x.fi, 0.0), 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
*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 4152kb

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: 4216kb

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: 4092kb

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: 4192kb

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: 4192kb

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: 4160kb

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: 4136kb

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: 0
Accepted
time: 0ms
memory: 4288kb

input:

3 8168 -766 1549 1256
-3951 -6425
-3874 -6439
-3911 -6389

output:

84.832861161006790

result:

ok found '84.8328612', expected '84.8328612', error '0.0000000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 4216kb

input:

8 2977 -3175 8766 2
-4868 7759
-4867 7925
-4867 7950
-4886 7952
-4979 7953
-5048 7877
-5003 7761
-4936 7759

output:

0.327860646906108

result:

ok found '0.3278606', expected '0.3278606', error '0.0000000'

Test #11:

score: 0
Accepted
time: 0ms
memory: 4192kb

input:

13 -1715 -4640 267 8651
272 6659
264 6660
208 6664
108 6625
107 6621
93 6564
90 6551
90 6485
124 6474
219 6477
283 6525
288 6591
286 6657

output:

153.589622784682462

result:

ok found '153.5896228', expected '153.5896228', error '0.0000000'

Test #12:

score: 0
Accepted
time: 0ms
memory: 4172kb

input:

8 -9743 -7629 775 7
-194 981
-191 1720
-193 1845
-705 1929
-959 1950
-1131 1894
-1151 1604
-1031 1020

output:

2.046006204355636

result:

ok found '2.0460062', expected '2.0460062', error '0.0000000'

Test #13:

score: 0
Accepted
time: 0ms
memory: 4096kb

input:

9 -6770 -1426 3491 1918
-2118 2886
-2063 3245
-2122 3709
-2129 3737
-2850 3718
-2984 3650
-3042 3462
-3028 2972
-2688 2888

output:

822.241184963715568

result:

ok found '822.2411850', expected '822.2411850', error '0.0000000'

Test #14:

score: 0
Accepted
time: 0ms
memory: 4228kb

input:

12 1616 -7384 5256 10
-5607 2623
-5838 2843
-6117 2986
-6592 3169
-7129 3120
-7334 3069
-7406 2295
-7369 1712
-7091 1287
-6312 1252
-5596 1592
-5457 2088

output:

3.038765377139073

result:

ok found '3.0387654', expected '3.0387654', error '0.0000000'

Test #15:

score: 0
Accepted
time: 0ms
memory: 4156kb

input:

10 -4546 5056 639 2996
4851 -3506
6078 -3725
6629 -3674
6775 -3296
6743 -2137
6585 -1866
5334 -1837
4950 -2020
4873 -2260
4852 -3240

output:

262.423969078937660

result:

ok found '262.4239691', expected '262.4239691', error '0.0000000'

Test #16:

score: 0
Accepted
time: 0ms
memory: 4288kb

input:

20 4847 -6818 2502 2
-2164 -3844
-2453 -3826
-4654 -3818
-5073 -3829
-5212 -3833
-5828 -3921
-5889 -6065
-5896 -6716
-5877 -7349
-5855 -7457
-5619 -7711
-5485 -7786
-3743 -7809
-2345 -7747
-2075 -7682
-1960 -7364
-1900 -7015
-1901 -6391
-1922 -4091
-1968 -4028

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #17:

score: 0
Accepted
time: 0ms
memory: 4160kb

input:

14 -1792 -5751 2349 4072
-3697 -4432
-4268 -4431
-6475 -4433
-7140 -4464
-7320 -4526
-7354 -5333
-7357 -5731
-7366 -7076
-7346 -7868
-7218 -8415
-4044 -8407
-3412 -8398
-3388 -7296
-3391 -4497

output:

758.966768347891843

result:

ok found '758.9667683', expected '758.9667683', error '0.0000000'

Test #18:

score: 0
Accepted
time: 0ms
memory: 4096kb

input:

23 8820 -5943 927 1
-1319 -4435
-1321 -297
-1361 -149
-1379 -119
-1619 13
-6579 12
-7090 11
-7184 -5
-7209 -18
-7277 -62
-7316 -672
-7316 -5095
-7295 -5877
-7273 -5921
-7250 -5955
-6569 -5967
-5927 -5975
-4278 -5977
-2646 -5978
-1477 -5965
-1472 -5962
-1404 -5892
-1334 -5809

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #19:

score: 0
Accepted
time: 0ms
memory: 4096kb

input:

22 -5664 7523 2588 8083
3456 2960
3446 2865
3433 2724
3432 615
3434 -1360
3446 -2929
3602 -2969
6204 -2972
8409 -2972
9227 -2969
9329 -2929
9375 -2890
9426 -2575
9432 2499
9432 2620
9390 2954
9386 2968
9277 3023
8340 3026
6809 3026
3634 3020
3600 3018

output:

3378.311740079398987

result:

ok found '3378.3117401', expected '3378.3117401', error '0.0000000'

Test #20:

score: 0
Accepted
time: 0ms
memory: 4192kb

input:

19 -1886 -3232 561 6
-8846 -7186
-8842 -7658
-8705 -7660
-1521 -7660
-1248 -7658
-1048 -7654
-906 -7650
-877 -7643
-858 -7619
-846 -7598
-846 -1489
-847 -277
-851 311
-1001 332
-1072 340
-7480 340
-8844 337
-8845 332
-8846 -9

output:

2.268233383460398

result:

ok found '2.2682334', expected '2.2682334', error '0.0000000'

Test #21:

score: 0
Accepted
time: 0ms
memory: 4204kb

input:

27 -8996 -3721 1431 7076
5671 -1552
3604 -1551
1370 -1551
-1106 -1552
-1845 -1553
-1945 -1582
-1964 -1649
-1981 -1924
-1981 -7875
-1980 -8365
-1979 -8628
-1977 -8988
-1974 -9316
-1963 -9548
-1871 -9550
-1288 -9551
5996 -9551
6006 -9455
6010 -9391
6012 -9343
6014 -9271
6015 -9144
6019 -7478
6019 -263...

output:

3442.559173706865295

result:

ok found '3442.5591737', expected '3442.5591737', error '0.0000000'

Test #22:

score: 0
Accepted
time: 0ms
memory: 4192kb

input:

5 -7413 -6822 8371 4
-8435 1969
-8446 1918
-8438 1885
-8390 1892
-8422 1955

output:

0.395157732679365

result:

ok found '0.3951577', expected '0.3951577', error '0.0000000'

Test #23:

score: 0
Accepted
time: 0ms
memory: 4288kb

input:

5 5998 6928 4304 9649
-9352 -3336
-9335 -3337
-9282 -3320
-9273 -3304
-9313 -3284

output:

1393.595878654907210

result:

ok found '1393.5958787', expected '1393.5958787', error '0.0000000'

Test #24:

score: 0
Accepted
time: 0ms
memory: 4156kb

input:

13 7526 -9874 3812 9
2735 4538
2673 4561
2663 4563
2652 4563
2609 4539
2607 4535
2582 4483
2593 4434
2601 4415
2711 4396
2735 4405
2749 4417
2777 4472

output:

3.299236026284501

result:

ok found '3.2992360', expected '3.2992360', error '0.0000000'

Test #25:

score: 0
Accepted
time: 0ms
memory: 4220kb

input:

9 1419 -6061 9067 634
-1331 -9405
-1206 -9456
-1165 -9391
-1157 -9359
-1184 -9294
-1252 -9276
-1312 -9299
-1329 -9336
-1336 -9354

output:

266.390380594422197

result:

ok found '266.3903806', expected '266.3903806', error '0.0000000'

Test #26:

score: -100
Wrong Answer
time: 0ms
memory: 4188kb

input:

15 -5029 6807 4505 5
5196 -3478
5116 -3556
5042 -3690
5048 -3936
5065 -4054
5286 -4238
5369 -4303
5565 -4330
5688 -4296
5868 -4016
5935 -3724
5909 -3628
5829 -3532
5702 -3457
5492 -3365

output:

1.442956883016480

result:

wrong answer 1st numbers differ - expected: '1.6678521', found: '1.4429569', error = '0.1348412'