QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#164010#6734. Click the Circleucup-team1209#WA 57ms3952kbC++203.5kb2023-09-04 18:06:572023-09-04 18:06:57

Judging History

你现在查看的是最新测评结果

  • [2023-09-04 18:06:57]
  • 评测
  • 测评结果:WA
  • 用时:57ms
  • 内存:3952kb
  • [2023-09-04 18:06:57]
  • 提交

answer

#include<bits/stdc++.h>
using u64 = unsigned long long;
using std::cin;
using std::cout;
const int mod = 998244353;
const int N = 1e3 + 10;
using db = long double;
using vec2 = std::complex<db>;
using cp = vec2;
const db eps = 1e-9;

int n;
vec2 a[N], b[N];
struct line { vec2 a, b; };
db cross(const vec2 & x, const vec2 & y) {
	return x.real() * y.imag() - x.imag() * y.real();
}
db dot(const vec2 & x, const vec2 & y) {
	return x.real() * y.real() + x.imag() * y.imag();
}

db dist(line x, vec2 y) {
	y -= x.a;
	x.b -= x.a;
	x.a -= x.a;
	if(abs(x.b) < eps) return abs(y);
	db prod = abs(x.b);
	y /= x.b;
	x.b = 1.;
	db min = std::min(abs(y), abs(y - x.b));
	if(0 <= y.real() && y.real() <= 1) {
		min = std::min(min, std::abs(y.imag()));
	}
	return min * prod;
}
db sgn(db x) {
	return x < -eps ? -1 : x > eps;
}
int ccw(vec2 a, vec2 b, vec2 c) {
	int sign = sgn(cross(b - a, c - a));
	if(sign == 0) {
		if(sgn(dot(b - a, c - a)) == -1) return 2;
		if(abs(c - a) > abs(b - a) + eps) return -2;
	}
	return sign;
}
bool isc(line x, line y) {
	return ccw(x.a, x.b, y.a) * ccw(x.a, x.b, y.b) <= eps &&
	ccw(y.a, y.b, x.a) * ccw(y.a, y.b, x.b) <= eps;
}
db dist(line x, line y) {
	if(isc(x, y)) return 0;
	db res = std::min({
		dist(y, x.a), dist(y, x.b),
		dist(x, y.a), dist(x, y.b),
	});
	return res;
}
db L[N], R[N];
db d, ra;

struct evt {
	db l, r;
	cp k, a;
};
std::vector<evt> v[N];

std::vector<evt> pb;

int main() {
	if(0) {
		line z(cp(0, 0), cp(0, 1));
		line y(cp(1, 0), cp(1, 1));
		cp o(0, 0);
		cout << dist(y, o) << '\n';
	}
	std::ios::sync_with_stdio(false), cin.tie(0);

#ifdef zqj
	freopen("4.in", "r", stdin);
#endif
	cin >> n >> d >> ra;
	for(int i = 1;i <= n;++i) {
		int type;
		db x, y, t;
		cin >> type;
		if(type == 1) {
			cin >> x >> y >> t;
			a[i] = cp(x, y);
			b[i] = cp(x, y);
			L[i] = R[i] = t;
			v[i] = {evt{ L[i] - d, R[i] + d, cp(0, 0), a[i] }};
		} else {
			cin >> x >> y;
			a[i] = cp(x, y);
			cin >> x >> y;
			b[i] = cp(x, y);
			cin >> L[i] >> R[i];
			cp k = (b[i] - a[i]) / (R[i] - L[i]);

			v[i].push_back(evt{L[i] - d, L[i], cp(0, 0), a[i]});

			v[i].push_back(evt{L[i], R[i], k, a[i] - k * L[i]});

			v[i].push_back(evt{R[i], R[i] + d, cp(0, 0), b[i]});
			pb.push_back({
				L[i] - d,
					R[i] + d,
					a[i],
					b[i]
			});
		}
	}
	int ans = 0;
	for(int i = 1;i <= n;++i) {
		for(int j = i + 1;j <= n;++j) {
			int ok = 0;
			for(auto x : v[i]) for(auto y : v[j]) {
				db l = std::max(x.l, y.l);
				db r = std::min(x.r, y.r);
				if(l - eps <= r) {
					cp kd = x.k - y.k;
					cp ad = x.a - y.a;
					line seg(kd * l + ad, kd * r + ad);
					if(dist(seg, cp(0, 0)) <= ra * 2 + eps) {
						ok = 1;
						break;
					}
				}
			}
			if(ok) ans += 1;
		}
	}
	for(int i = 1;i <= n;++i) {
		for(auto x : pb) {
			line ll(x.k, x.a);
			int ok = 0;
			for(auto y : v[i]) {
				db l = std::max(x.l, y.l);
				db r = std::min(x.r, y.r);
				if(l - eps <= r) {
					line seg(y.k * l + y.a, y.k * r + y.a);
					if(dist(seg, ll) <= ra * 2 + eps) {
						ok = 1;
						break;
					}
				}
			}
			if(ok) ans += 1;
		}
	}
	for(int i = 0;i < (int) pb.size();++i) {
		for(int j = 0;j < i;++j) {
			auto x = pb[i];
			auto y = pb[j];
			db l = std::max(x.l, y.l);
			db r = std::min(x.r, y.r);
			if(l - eps <= r) {
				line ll(x.k, x.a);
				line rr(y.k, y.a);
				if(dist(ll, rr) <= ra * 2 + eps) {
					ans += 1;
				}
			}

		}
	}
	cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3652kb

input:

2 1 1
1 1 1 2
1 2 2 3

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

2 1 1
1 1 1 2
1 3 2 3

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

2 1 1
1 3 3 2
2 5 5 5 1 2 4

output:

3

result:

ok 1 number(s): "3"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

2 1 1
2 1 1 1 5 2 4
2 5 5 5 1 2 4

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

2 1 1
2 10 1 10 20 2 4
2 1 10 20 10 2 4

output:

6

result:

ok 1 number(s): "6"

Test #6:

score: -100
Wrong Answer
time: 57ms
memory: 3952kb

input:

1000 8 4
1 8323 2820 943
1 8246 2850 944
1 8177 2880 941
1 8154 2866 944
2 8325 8146 2865 2846 943 944
1 8349 2891 939
2 8176 8344 2888 2692 940 945
1 8191 2732 945
1 8144 2668 945
2 8182 8191 2889 2844 939 940
1 8173 2687 941
1 8241 2870 945
2 8266 8344 2910 2667 942 943
1 8169 2863 939
1 8349 2921...

output:

21112

result:

wrong answer 1st numbers differ - expected: '22721', found: '21112'