QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#734847#9576. Ordainer of Inexorable JudgmentWillisWA 1ms4224kbC++2010.3kb2024-11-11 15:28:472024-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:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4224kb
  • [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'