QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#733548#9576. Ordainer of Inexorable Judgmentucup-team5008#WA 1ms4044kbC++234.9kb2024-11-10 19:48:102024-11-10 19:48:11

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:48:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4044kb
  • [2024-11-10 19:48:10]
  • 提交

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 dot(Point a, Point b) {
	return a.real() * b.real() + a.imag() * b.imag();
}

ld cross(Point a, Point b) {
	return (a.real() * b.imag() - a.imag() * b.real());
}

struct Line{
	Point a, b;
	Line(Point a, Point b) : a(a), b(b) {}
};

ld distance(Line l, Point p) {
	return fabs(cross(l.b - l.a, p - l.a) / abs(l.b - l.a));
}

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();
/*	{
		start = -start;
		rep(i,n) p[i] = -p[i];
	}
*/	
/*	{
		Point mul = Point(cos(100), sin(100));
		start *= mul;
		rep(i,n) p[i] *= mul;
	}
*/	{
		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] << " " << atan2l(cr.imag(), cr.real()) << endl;
			auto val = atan2l(cr.imag(), cr.real());
			if(equal(val, M_PI)) val = -M_PI;
			data.eb(val, i);
		}
	}
	{
		auto val = atan2l(start.imag(), start.real());
		if(equal(val, M_PI)) val = -M_PI;
		data.eb(val-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(dot(p[i], start) > -EPS && distance(Line(0, start), p[i]) < 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: 3964kb

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

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

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

input:

3 10000 10000 1 10000
10000 9999
10000 10000
9999 10000

output:

0.384241300290122

result:

ok found '0.3842413', expected '0.3842413', error '0.0000000'

Test #5:

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

input:

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

output:

2500.240670009608062

result:

ok found '2500.2406700', expected '2500.2406700', error '0.0000000'

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 3904kb

input:

4 1 0 1 10000
-2 3400
-4 10000
-4 -10000
-2 -3400

output:

1.872352644233853

result:

wrong answer 1st numbers differ - expected: '4999.2191154', found: '1.8723526', error = '0.9996255'