QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#33339 | #4226. Cookie Cutter | flower_and_qingyu# | TL | 2ms | 4084kb | C++14 | 4.1kb | 2022-05-31 14:22:47 | 2022-05-31 21:56:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr double PI = acos(-1), eps = 1e-9;
inline int sgn(double x) {return fabs(x) < eps ? 0 : (x < 0 ? -1 : 1);}
struct Point {
double x, y;
friend Point operator - (Point a, Point b) {return {a.x - b.x, a.y - b.y};}
friend Point operator + (Point a, Point b) {return {a.x + b.x, a.y + b.y};}
friend Point operator * (Point a, double x) {return {a.x * x, a.y * x};}
friend Point operator / (Point a, double x) {return {a.x / x, a.y / x};}
double arg() {
double r = atan2(y, x);
if(r < 0) r += 2 * PI;
return r;
}
};
struct Line {
Point s, t;
Point v() {return t - s;}
};
double cross(Point u, Point v) {
return u.x * v.y - u.y * v.x;
}
Point inter(Line p, Line q) {
double s1 = cross(q.s - p.s, q.t - p.s);
double s2 = cross(q.t - p.t, q.s - p.t);
assert(sgn(s1 + s2) != 0);
return (p.s * s2 + p.t * s1) / (s1 + s2);
}
bool onleft(Point p, Line q) {
return sgn(cross(q.t - q.s, p - q.s)) > 0;
}
bool onright(Point p, Line q) {
return sgn(cross(q.t - q.s, p - q.s)) < 0;
}
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
vector<Point> a(m);
for(int i = 0; i < m; i ++) {
int x, y;
cin >> x >> y;
a[i].x = x, a[i].y = y;
// cin >> a[i].x >> a[i].y;
}
vector<Line> l;
l.emplace_back((Line) {0, 0, n, 0});
l.emplace_back((Line) {n, 0, n, n});
l.emplace_back((Line) {n, n, 0, n});
l.emplace_back((Line) {0, n, 0, 0});
auto calc = [&] (Point u, Point v) {
vector<Line> cur = l;
cur.emplace_back((Line) {u, v});
sort(cur.begin(), cur.end(), [&] (Line u, Line v) {return u.v().arg() < v.v().arg();});
vector<Line> nxt;
for(int i = 0; i < cur.size(); i ++) {
if(!nxt.empty() && sgn(nxt.back().v().arg() - cur[i].v().arg()) == 0){
if(onleft(cur[i].t, nxt.back())) {
nxt.pop_back();
}
}
nxt.emplace_back(cur[i]);
}
cur = nxt;
deque<Line> q;
for(auto u : cur) {
while(q.size() > 1 && onright(inter(q[q.size() - 2], q.back()), u)) q.pop_back();
while(q.size() > 1 && onright(inter(q[0], q[1]), u)) q.pop_front();
q.push_back(u);
}
while(q.size() > 2 && onright(inter(q.back(), q[q.size() - 2]), q[0])) q.pop_back();
vector<Point> res;
for(int i = 0; i < q.size(); i ++) {
res.emplace_back(inter(q[i], q[(i + 1) % q.size()]));
}
double area = 0;
for(int i = 2; i < res.size(); i ++) area += cross(res[i] - res[i - 1], res[0] - res[i - 1]);
return area / 2;
};
if(m == 1) {
vector<Point> ret, cur;
ret.emplace_back((Point) {0, 0});
ret.emplace_back((Point) {0, n});
ret.emplace_back((Point) {n, 0});
ret.emplace_back((Point) {n, n});
cur = ret;
for(auto u : ret) {
for(auto v : l) {
Point x = inter(v, (Line) {u, a[0]});
if(x.x > 0 && x.x < n && x.y > 0 && x.y < n) cur.emplace_back(x);
}
}
Point u = a[0];
sort(cur.begin(), cur.end(), [&] (Point x, Point y) {
return (x - u) .arg() < (y - u).arg();
});
double ans = -1;
for(int i = 0; i < cur.size(); i ++) {
Point l = cur[i], r = cur[(i + 1) % cur.size()];
// cout << u.x << ' ' << u.y << ' ' << v.x << ' ' << v.y << '\n';
for(int i = 0; i < 200; i ++) {
Point lmid = (l + l + r) / 3, rmid = (l + r + r) / 3;
if(calc(u, lmid) < calc(u, rmid)) r = rmid;
else l = lmid;
}
ans = max(ans, 1 - calc(u, l) / n / n);
}
cout << fixed << setprecision(10) << ans << '\n';
return 0;
}
double ans = -1;
for(int i = 0; i < m; i ++) {
Point u = a[i];
vector<Point> b = a;
b.erase(b.begin() + i);
sort(b.begin(), b.end(), [&] (Point x, Point y) {
return (x - u).arg() < (y - u).arg();
});
int pl = 0;
for(int i = 0; i < b.size(); i ++) {
while(pl < b.size() && sgn(cross(b[i] - u, b[pl] - u)) >= 0) pl ++;
int k = pl - i + 1;
// cout << k << ' ' << m << '\n';
// assert(calc(u, b[i]) >= 0);
// cout << u.x << ' ' << u.y << ' ' << b[i].x << ' ' << b[i].y << ' ' << k << '\n';
ans = max(ans, 1.0 * k / m - calc(u, b[i]) / n / n);
}
}
cout << fixed << setprecision(10) << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 4084kb
input:
5 8 1 1 1 2 1 3 2 1 3 1 3 4 4 1 4 2
output:
0.3750000000
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...