QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#734546#9576. Ordainer of Inexorable JudgmentWillisWA 0ms4412kbC++208.5kb2024-11-11 12:30:332024-11-11 12:30:35

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 12:30:35]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4412kb
  • [2024-11-11 12:30:33]
  • 提交

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 ld;
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-9;
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};
	}
};

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))
{
	double 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.disToLine(x).fi);
	}
	return Mindis;
}

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;
	}
	if (contain(p, n, Point(0, 0)) || sgn(1.0 * d - calcdis()) >= 0)
	{
		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;
	double thetal = atan2(l.y, l.x), thetar = atan2(r.y, r.x);
	if(sgn(thetal)<0)
		thetal += 2 * pi;
	if(sgn(thetar)<0)
		thetar += 2 * pi;
	thetal -= asin(d / dis(Point(0, 0), l));
	thetar += asin(d / dis(Point(0, 0), r));
	vector<pair<double, double>> inter;
	//cout << thetal << " " << thetar << endl;
	if (cross == false)
	{
		if (thetal <= 0)
			inter.pb(PD(0, thetar)), inter.pb(PD(2 * pi - thetal, 2 * pi));
		else if (thetar >= 2 * pi)
			inter.pb(PD(0, 2 * pi - thetar)), inter.pb(PD(thetal, 2 * pi));
		else
			inter.pb(PD(thetal, thetar));
	}
	else
		inter.pb(PD(0, thetar)), inter.pb(PD(thetal, 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;
	double theta_begin = atan2(face.y, face.x);
	vector<pair<double, double>> inter2 = inter;
	for (int i = 0; i < inter.size(); i++)
	{
		//cout << inter[i].fi << " " << inter[i].se << endl;
		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 += 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
*/

详细

Test #1:

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

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

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

input:

3 1 0 1 10000
1 2
2 1
2 2

output:

2500.707752257475477

result:

ok found '2500.7077523', expected '2500.7077523', error '0.0000000'

Test #4:

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

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: -100
Wrong Answer
time: 0ms
memory: 4124kb

input:

3 -10000 -10000 10000 10000
-10000 -9999
-10000 -10000
-9999 -10000

output:

10000

result:

wrong answer 1st numbers differ - expected: '2500.2406700', found: '10000.0000000', error = '2.9996150'