QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#555284 | #4226. Cookie Cutter | Fortitude# | TL | 1ms | 4072kb | C++23 | 3.0kb | 2024-09-09 21:26:48 | 2024-09-09 21:26:48 |
Judging History
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