QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#555284#4226. Cookie CutterFortitude#TL 1ms4072kbC++233.0kb2024-09-09 21:26:482024-09-09 21:26:48

Judging History

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

  • [2024-09-09 21:26:48]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4072kb
  • [2024-09-09 21:26:48]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
using ll = long long;
using ld = double;
using pii = pair <int, int>;

template<class T> struct Point{
	T x, y;
	Point(T x = 0, T y = 0): x(x), y(y) {}
	using P = Point;
	P operator - (P p) const { return P(x - p.x, y - p.y); }
	P operator + (P p) const { return P(x + p.x, y + p.y); }
	P operator * (T d) const { return P(x * d, y * d); }
	P operator / (T d) const { return P(x / d, y / d); }
	T cross(P p) const { return x * p.y - y * p.x; }
	T cross(P a, P b) const { return (a - *this).cross(b - *this); }
	bool side() const {
		if(y == 0) return x < 0;
		return y < 0;
	}
	bool operator < (P p) const{
		if(side() == p.side()) return cross(p) > 0;
		return p.side();
	}
	friend ostream& operator << (ostream& os, P p){
		return os << '(' << p.x << ", " << p.y << ')';
	}
};
template<class P> inline pair<int, P> lineInter(P s1, P e1, P s2, P e2){
	auto d = (e1 - s1).cross(e2 - s2);
	if(d == 0) return {-(s1.cross(e1, s2) == 0), P{0, 0}};
	auto p = s2.cross(e1, e2), q = s2.cross(e2, s1);
	return {1, (s1 * p + e1 * q) / d};
}
template<class P> inline vector<P> polygonCut(vector<P> poly, P s, P e){
	vector<P> res;
	for(int i = 0; i < sz(poly); i++){
		P cur = poly[i], prev = i ? poly[i - 1] : poly.back();
		bool side = s.cross(e, cur) < 0;
		if(side != (s.cross(e, prev) < 0))
			res.pb(lineInter(s, e, cur, prev).second);
		if(side) res.pb(cur);
	}
	return res;
}
using P = Point<ll>;
const int N = 3e3;

int n, W;
P a[N];

inline ld get(Point<ld> c, Point<ld> d){
	vector<Point<ld>> ch = {
		Point<ld>(0, 0),
		Point<ld>(W, 0),
		Point<ld>(W, W),
		Point<ld>(0, W)
	};
	ch = polygonCut(ch, c, c - d);
	ld res = 0;
	for(int i = 0; i < sz(ch); i++) res += ch[i].cross(ch[(i + 1) % sz(ch)]);
	return res / 2;
}

inline ld calc(int v, P L, P R){
	Point<ld> c{a[v].x, a[v].y}, l{L.x, L.y}, r{R.x, R.y};
	ld tl = 0, tr = 1;
	for(int i = 0; i < 2; i++){
		ld m1 = tl + (tr - tl) / 3;
		ld m2 = tr - (tr - tl) / 3;
		if(get(c, l * m1 + r * (1 - m1)) < get(c, l * m2 + r * (1 - m2))) tr = m2;
		else tl = m1;
	}
	return get(c, l * tl + r * (1 - tl));
}

main() {
	ios :: sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> W >> n;
	for(int i = 0; i < n; i++) cin >> a[i].x >> a[i].y;
	ld ans = 0;
	for(int i = 0; i < n; i++){
		vector<pair<P, int>> vec = {
			{P{0, 1}, 0},
			{P{0, -1}, 0},
			{P{1, 0}, 0},
			{P{-1, 0}, 0}
		};
		for(int j = 0; j < n; j++){
			if(i == j) continue;
			vec.pb({a[i] - a[j], -1});
			vec.pb({a[j] - a[i], 1});
		}
		sort(all(vec));
		for(int j = 0; j < sz(vec); j++) vec[j].second *= -1;
		int cur = 0;
		for(int j = 0; j < n; j++) cur += !(a[j] - a[i]).side();
		for(int j = 0; j < sz(vec); j++){
			cur += vec[j].second;
			ans = max(ans, ld(cur) / n - calc(i, vec[j].first, vec[(j + 1) % sz(vec)].first) / W / W);
		}
	}
	cout << fixed << setprecision(9) << ans;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

0.375000000

result:

ok found '0.3750000', expected '0.3750000', error '0.0000000'

Test #2:

score: -100
Time Limit Exceeded

input:

10000 2916
93 93
93 278
93 463
93 649
93 834
93 1019
93 1204
93 1389
93 1574
93 1760
93 1945
93 2130
93 2315
93 2500
93 2685
93 2871
93 3056
93 3241
93 3426
93 3611
93 3796
93 3982
93 4167
93 4352
93 4537
93 4722
93 4907
93 5093
93 5278
93 5463
93 5648
93 5833
93 6018
93 6204
93 6389
93 6574
93 6759...

output:

0.009344444

result: