QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#280630 | #7783. Military Maneuver | ucup-team1198# | WA | 804ms | 4044kb | C++14 | 9.2kb | 2023-12-09 17:20:08 | 2023-12-09 17:20:08 |
Judging History
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;
struct Point {
long double x, y;
Point(long double x, long double y): x(x), y(y) {}
Point(): x(0ll), y(0ll) {}
};
Point operator+(const Point& first, const Point& second) {
return Point(first.x + second.x, first.y + second.y);
}
Point operator-(const Point& first, const Point& second) {
return Point(first.x - second.x, first.y - second.y);
}
long double cross(const Point& first, const Point& second) {
return first.x * second.y - first.y * second.x;
}
long double dot(const Point& first, const Point& second) {
return first.x * second.x + first.y * second.y;
}
long double sqrlen(const Point& P) {
return P.x * P.x + P.y * P.y;
}
long double len(const Point& P) {
return sqrtl(sqrlen(P));
}
const long double INF = 1e9;
const long double EPS = 1e-7;
struct Line{
long double a;
long double b;
long double c;
Line(long double a, long double b, long double c): a(a), b(b), c(c) {}
Point get_perp() const {
return Point(a, b);
}
long double get_y_by_x(long double x) const {
return (-c - a * x) / b;
}
};
long double inter(const Line& l1, const Line& l2) {
return (-l1.c * l2.b + l2.c * l1.b) / (l1.a * l2.b - l2.a * l1.b);
}
// ax + by+c>=0
vector<Point> halfplane_inter(vector<Line>& lines) {
long double min_x = -INF;
long double max_x = INF;
vector<Line> up;
vector<Line> down;
for (Line l : lines) {
if (l.b == 0) {
if (l.a > 0) {
min_x = max(min_x, -l.c / l.a);
} else {
max_x = min(max_x, -l.c / l.a);
}
} else if (l.b > 0) {
up.emplace_back(l);
} else {
down.emplace_back(l);
}
}
if (max_x - min_x < EPS) {
return {};
}
sort(up.begin(), up.end(), [](const Line& l1, const Line& l2) {
if (abs(cross(l1.get_perp(), l2.get_perp())) < EPS) {
// parallel
return l1.c / len(l1.get_perp()) < l2.c / len(l2.get_perp());
}
return cross(l1.get_perp(), l2.get_perp()) > 0;
});
vector<Line> up_hull;
vector<long double> up_xs;
for (Line l : up) {
// skip parallel
if (!up_hull.empty() && abs(cross(up_hull.back().get_perp(), l.get_perp())) < EPS)
continue;
if (up_hull.empty()) {
up_hull.emplace_back(l);
continue;
}
while (!up_xs.empty() && EPS >= inter(up_hull.back(), l) - up_xs.back()) {
up_hull.pop_back();
up_xs.pop_back();
}
up_xs.emplace_back(inter(up_hull.back(), l));
up_hull.emplace_back(l);
}
sort(down.begin(), down.end(), [](const Line& l1, const Line& l2) {
if (abs(cross(l1.get_perp(), l2.get_perp())) < EPS) {
// parallel
return l1.c / len(l1.get_perp()) < l2.c / len(l2.get_perp());
}
return cross(l1.get_perp(), l2.get_perp()) < 0;
});
vector<Line> down_hull;
vector<long double> down_xs;
for (Line l : down) {
// skip parallel
if (!down_hull.empty() && abs(cross(down_hull.back().get_perp(), l.get_perp())) < EPS)
continue;
if (down_hull.empty()) {
down_hull.emplace_back(l);
continue;
}
while (!down_xs.empty() && EPS >= inter(down_hull.back(), l) - down_xs.back()) {
down_hull.pop_back();
down_xs.pop_back();
}
down_xs.emplace_back(inter(down_hull.back(), l));
down_hull.emplace_back(l);
}
int i1 = 0;
int i2 = 0;
while (i1 < up_xs.size() && up_xs[i1] < min_x)
++i1;
while (i2 < down_xs.size() && down_xs[i2] < min_x)
++i2;
long double prev = min_x;
vector<Point> points;
auto try_pushing_points = [&](long double x, int i1, int i2) {
long double y_up = up_hull[i1].get_y_by_x(x);
long double y_down = down_hull[i2].get_y_by_x(x);
if (y_down - y_up > EPS) {
points.emplace_back(x, y_up);
points.emplace_back(x, y_down);
}
if (abs(cross(up_hull[i1].get_perp(), down_hull[i2].get_perp())) > EPS) {
long double cur_x = inter(up_hull[i1], down_hull[i2]);
if (prev <= cur_x && cur_x <= x)
points.emplace_back(cur_x, up_hull[i1].get_y_by_x(cur_x));
}
prev = x;
};
try_pushing_points(min_x, i1, i2);
while (i1 < up_xs.size() || i2 < down_xs.size()) {
long double cur_x = 0;
int old_i1 = i1;
int old_i2 = i2;
if (i1 < up_xs.size() && (i2 == down_xs.size() || up_xs[i1] < down_xs[i2])) {
cur_x = up_xs[i1];
++i1;
} else {
cur_x = down_xs[i2];
++i2;
}
if (cur_x > max_x)
cur_x = max_x;
try_pushing_points(cur_x, old_i1, old_i2);
if (cur_x == max_x)
break;
}
if (prev < max_x) {
try_pushing_points(max_x, i1, i2);
}
return points;
}
void srt(vector<Point>& arr) {
Point p0 = arr[0];
sort(arr.begin(), arr.end(), [&p0](Point a, Point b) {
if (cross(a - p0, b - p0) == 0) {
return sqrlen(a - p0) < sqrlen(b - p0);
}
return cross(a - p0, b - p0) < 0;
});
}
long double get(const vector<Point>& arr, int alpha) {
int k = arr.size();
long double ans = 0;
long double minx = 1e9, maxx = -1e9;
for (int i = 0; i < k; ++i) {
minx = min(minx, arr[i].x);
maxx = max(maxx, arr[i].x);
}
for (int i = 0; i < k; ++i) {
long double x1 = arr[i].x;
long double x2 = arr[(i + 1) % k].x;
long double y1 = arr[i].y;
long double y2 = arr[(i + 1) % k].y;
if (abs(x2 - x1) < 1e-12 && (abs(x1 - minx) < 1e-12 || abs(x1 - maxx) < 1e-12)) continue;
long double dlta = 1;
long double add = x1;
for (int i = 1; i <= alpha; ++i) {
dlta = dlta * x2 + add;
add *= x1;
}
long double dlta2 = dlta * x2 + add;
ans += dlta / (alpha + 1) * (y1 * x2 - x1 * y2) + dlta2 / (alpha + 2) * (y2 - y1);
}
return ans;
}
int main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#endif
int xl, yl, xr, yr;
cin >> xl >> yl >> xr >> yr;
int n;
cin >> n;
vector<array<int, 2>> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i][0] >> arr[i][1];
}
long double ans = 0;
for (int i = 0; i < n; ++i) {
vector<Line> hp;
hp.push_back({1, 0, -xl});
hp.push_back({-1, 0, xr});
hp.push_back({0, 1, -yl});
hp.push_back({0, -1, yr});
for (int j = 0; j < n; ++j) {
if (i == j) continue;
long double A = arr[j][0] - arr[i][0];
long double B = arr[j][1] - arr[i][1];
long double x = arr[i][0] + arr[j][0];
long double y = arr[i][1] + arr[j][1];
x /= 2;
y /= 2;
long double C = -A * x - B * y;
/// cerr << i << ": " << A << " " << B << " " << C << endl;
/// cerr << A * arr[j][0] + B * arr[j][1] + C << endl;
hp.push_back({A, B, C});
}
auto res = halfplane_inter(hp);
if (!res.empty()) {
srt(res);
/**cerr << "res: " << endl;
for (auto elem : res) {
cerr << elem.x << " " << elem.y << endl;
}*/
long double I2 = get(res, 2);
long double I1 = get(res, 1);
long double I0 = get(res, 0);
/// cerr << i << ": " << I0 << " " << I1 << " " << I2 << endl;
ans += I2 - 2 * I1 * arr[i][0] + I0 * arr[i][0] * arr[i][0];
for (Point& p : res) {
swap(p.x, p.y);
}
reverse(res.begin(), res.end());
I2 = get(res, 2);
I1 = get(res, 1);
I0 = get(res, 0);
/// cerr << i << ": " << I0 << " " << I1 << " " << I2 << endl;
ans += I2 - 2 * I1 * arr[i][1] + I0 * arr[i][1] * arr[i][1];
}
hp.clear();
hp.push_back({1, 0, -xl});
hp.push_back({-1, 0, xr});
hp.push_back({0, 1, -yl});
hp.push_back({0, -1, yr});
for (int j = 0; j < n; ++j) {
if (i == j) continue;
long double A = arr[j][0] - arr[i][0];
long double B = arr[j][1] - arr[i][1];
long double x = arr[i][0] + arr[j][0];
long double y = arr[i][1] + arr[j][1];
x /= 2;
y /= 2;
long double C = -A * x - B * y;
hp.push_back({-A, -B, -C});
}
res = halfplane_inter(hp);
if (!res.empty()) {
srt(res);
/**cerr << "res: " << endl;
for (auto elem : res) {
cerr << elem.x << " " << elem.y << endl;
}*/
long double I2 = get(res, 2);
long double I1 = get(res, 1);
long double I0 = get(res, 0);
ans -= I2 - 2 * I1 * arr[i][0] + I0 * arr[i][0] * arr[i][0];
for (Point& p : res) {
swap(p.x, p.y);
}
reverse(res.begin(), res.end());
I2 = get(res, 2);
I1 = get(res, 1);
I0 = get(res, 0);
ans -= I2 - 2 * I1 * arr[i][1] + I0 * arr[i][1] * arr[i][1];
}
}
ans /= (xr - xl) * (yr - yl);
long double PI = 3.141592653589793238;
cout << fixed << setprecision(20);
cout << PI * ans << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3844kb
input:
0 0 2 2 2 3 1 1 3
output:
8.37758040957278164382
result:
ok found '8.3775804', expected '8.3775804', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
0 0 2 2 2 5 1 1 3
output:
37.69911184307751739198
result:
ok found '37.6991118', expected '37.6991118', error '0.0000000'
Test #3:
score: -100
Wrong Answer
time: 804ms
memory: 4044kb
input:
-2911 2151 336 5941 2000 -83 79 -94 47 48 -29 -47 64 84 75 -44 -86 -58 -11 -31 58 20 53 80 -19 -82 74 -60 -26 8 -68 -42 -61 -14 12 -58 -18 92 10 35 -26 71 64 76 89 -80 6 70 4 -96 -99 95 -80 -3 -22 71 -89 -75 17 -35 -82 -59 95 60 48 -74 50 -82 90 -26 5 -75 -31 -45 85 85 14 -70 -57 59 46 55 13 -23 60 ...
output:
4980913.46837657743753879913
result:
wrong answer 1st numbers differ - expected: '6657168.1428534', found: '4980913.4683766', error = '0.2517970'