QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#362707 | #8513. Insects, Mathematics, Accuracy, and Efficiency | ucup-team1198# | RE | 0ms | 0kb | C++20 | 5.5kb | 2024-03-23 16:49:18 | 2024-03-23 16:49:19 |
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
using ld = long double;
struct Vector {
ld x;
ld y;
Vector(ld x = 0, ld y = 0): x(x), y(y) {}
Vector(const Vector& a, const Vector& b): x(b.x - a.x), y(b.y - a.y) {}
ld sqlen() const { return x * x + y * y; }
ld len() const { return hypotl(x, y); }
ld ang() const { return atan2l(y, x); }
Vector nrm() const { return Vector(-y, x); }
};
Vector operator-(const Vector& a, const Vector& b) {
return Vector(b, a);
}
Vector operator+(const Vector& a, const Vector& b) {
return {a.x + b.x, a.y + b.y};
}
Vector operator*(const Vector& a, ld k) {
return {a.x * k, a.y * k};
}
Vector operator/(const Vector& a, ld k) {
return {a.x / k, a.y / k};
}
ld operator%(const Vector& a, const Vector& b) {
return a.x * b.y - a.y * b.x;
}
ld operator*(const Vector& a, const Vector& b) {
return a.x * b.x + a.y * b.y;
}
istream& operator>>(istream& in, Vector& v) {
in >> v.x >> v.y;
return in;
}
const ld EPS = 1e-9, PI = atan2l(0, -1);
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
/// cout.tie(0);
cout << fixed << setprecision(20);
int n;
cin >> n;
if (n == 1) {
cout << "0.0";
return 0;
}
ld R;
cin >> R;
vector<Vector> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
Vector min_p = arr[0];
for (int i = 0; i < n; ++i) {
if (arr[i].x < min_p.x) {
min_p = arr[i];
} else if (arr[i].x == min_p.x && arr[i].y < min_p.y) {
min_p = arr[i];
}
}
sort(arr.begin(), arr.end(), [&](Vector u, Vector v) {
if (abs((u - min_p) % (v - min_p)) < EPS) {
return (u - min_p).sqlen() < (v - min_p).sqlen();
}
return (u - min_p) % (v - min_p) < 0;
});
arr.push_back(arr[0]);
vector<Vector> st;
int sz = 0;
for (Vector p : arr) {
int threshold = 2;
if (abs(p.x - min_p.x) < EPS && abs(p.y - min_p.y) < EPS) {
threshold = 3;
}
while (sz >= threshold && (p - st[sz - 2]) % (st[sz - 1] - st[sz - 2]) < EPS) {
--sz;
st.pop_back();
}
++sz;
st.push_back(p);
}
st.pop_back();
vector<Vector> p = st;
n = p.size();
/**for (int i = 0; i < n; ++i) {
cout << p[i].x << " " << p[i].y << endl;
}*/
vector<ld> pref(n + 1);
for (int i = 0; i < n; ++i) {
pref[i + 1] = pref[i] + (p[i] % p[(i + 1) % n]);
}
vector<pair<ld, int>> ev;
for (int i = 0; i < n; ++i) {
Vector pt = p[i];
Vector v = p[(i + 1) % n] - pt;
ld d2 = (v % pt) * (v % pt) / v.sqlen();
ld l = sqrtl(max((ld)0, R * R - d2));
Vector n = v.nrm();
Vector h = n * (v % pt) / v.sqlen();
Vector start = h + v * l / v.len();
Vector fin = h - v * l / v.len();
ev.push_back({start.ang(), i + 1});
ev.push_back({fin.ang(), -i - 1});
}
sort(ev.begin(), ev.end());
vector<int> visible(n);
vector<int> li(n), ri(n);
for (int i = 0; i < 2 * n; ++i) {
if (ev[i].second > 0) {
li[ev[i].second - 1] = i;
} else {
ri[-ev[i].second - 1] = i;
}
}
for (int i = 0; i < n; ++i) {
/// cerr << li[i] << " " << ri[i] << "\n";
if (li[i] > ri[i]) {
visible[i] = 1;
}
}
int l = -1, r = -1;
for (int i = 0; i < n; ++i) {
int i1 = (i + n - 1) % n;
if (visible[i] && !visible[i1]) {
assert(l == -1);
l = i;
}
if (!visible[i] && visible[i1]) {
assert(r == -1);
r = i;
}
}
assert(l != -1 && r != -1);
/// cerr << "start: " << l << " " << r << endl;
auto get = [&](ld ang) {
Vector pt = {cosl(ang), sinl(ang)};
pt = pt * R;
ld area = p[l] % pt + pt % p[r];
if (l > r) {
area += pref[l] - pref[r];
} else {
area += pref[n] + pref[l] - pref[r];
}
/// cout << ang << ": " << abs(area) << endl;
/// cout << l << " " << r << endl;
/// cout << pref[n] << " " << pref[l] << " " << pref[r] << endl;
return abs(area);
};
vector<pair<ld, int>> ev1;
ev1.push_back({-PI, 0});
for (auto elem : ev) {
ev1.push_back(elem);
}
ev1.push_back({PI, 0});
ev = ev1;
ld ans = 0;
for (int i = 0; i + 1 < (int)ev1.size(); ++i) {
ld L = ev[i].first, R = ev[i + 1].first;
if (l != r) {
/// cerr << "in L" << endl;
ans = max(ans, get(L));
/// cerr << (p[r] - p[l]).nrm().x << " " << (p[r] - p[l]).nrm().y << endl;
ld M = (p[r] - p[l]).nrm().ang();
/// cerr << M << endl;
if (M > L && M < R) {
ans = max(ans, get(M));
}
}
if (ev[i + 1].second > 0) {
l = (l - 1 + n) % n;
} else if (ev[i + 1].second < 0) {
r = (r - 1 + n) % n;
}
}
cout << ans / 2;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
4 1000 -1000 0 0 0 1000 0 0 -1000