QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#942334 | #10161. Symmetric Boundary | ElevenX | WA | 1ms | 4096kb | C++20 | 5.3kb | 2025-03-19 04:36:14 | 2025-03-19 04:36:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef double T;
const T EPS = 1e-8;
struct Point {
T x, y;
Point() {}
Point(T x, T y) : x(x), y(y) {}
bool operator<(const Point &p) const { return tie(x, y) < tie(p.x, p.y); }
bool operator==(const Point &p) const { return abs(x - p.x) <= EPS && abs(y - p.y) <= EPS; }
};
Point operator-(const Point &p) { return Point(-p.x, -p.y); }
Point operator-(const Point &a, const Point &b) { return Point(a.x - b.x, a.y - b.y); }
T cross(const Point &a, const Point &b) { return a.x * b.y - a.y * b.x; }
T dot(const Point &a, const Point &b) { return a.x * b.x + a.y * b.y; }
T sqlen(const Point &a) { return dot(a, a); }
vector<Point> convexHull(vector<Point> pts) {
sort(pts.begin(), pts.end());
pts.erase(unique(pts.begin(), pts.end()), pts.end());
if (pts.size() <= 1) return pts;
vector<Point> h;
for (int phase = 0; phase < 2; ++phase) {
auto start = h.size();
for (auto &p : pts) {
while (h.size() >= start + 2 && cross(h.back() - h[h.size() - 2], p - h[h.size() - 2]) <= EPS)
h.pop_back();
h.push_back(p);
}
h.pop_back();
reverse(pts.begin(), pts.end());
}
return h;
}
bool onSegment(const Point &a, const Point &b, const Point &p) {
if (abs(cross(b - a, p - a)) > EPS) return false;
T d = dot(b - a, p - a);
return d > -EPS && d < sqlen(b - a) + EPS;
}
bool isOnBoundary(const vector<Point> &hull, const Point &p) {
int n = hull.size();
for (int i = 0; i < n; ++i) {
Point a = hull[i], b = hull[(i + 1) % n];
if (onSegment(a, b, p)) return true;
}
for (const Point &q : hull)
if (abs(p.x - q.x) <= EPS && abs(p.y - q.y) <= EPS)
return true;
return false;
}
string formatNumber(double value) {
stringstream ss;
ss << fixed << setprecision(10) << value;
string s = ss.str();
size_t dot_pos = s.find('.');
if (dot_pos != string::npos) {
size_t last_non_zero = s.find_last_not_of('0', s.size() - 1);
if (last_non_zero == string::npos) {
s = s.substr(0, dot_pos + 2);
} else if (last_non_zero == dot_pos) {
s = s.substr(0, dot_pos + 2);
} else {
s = s.substr(0, last_non_zero + 1);
if (s.back() == '.') {
s += "0";
}
}
}
return s;
}
int main() {
int n;
cin >> n;
vector<Point> pts(n);
for (int i = 0; i < n; ++i) {
cin >> pts[i].x >> pts[i].y;
}
double min_area = -1;
set<pair<double, double>> tried_centers;
// Check all midpoints of pairs of distinct vertices
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) continue;
Point p = pts[i], q = pts[j];
double cx = (p.x + q.x) / 2.0;
double cy = (p.y + q.y) / 2.0;
if (tried_centers.count({cx, cy})) continue;
tried_centers.insert({cx, cy});
vector<Point> all = pts;
for (const Point &pt : pts) {
Point sym(2 * cx - pt.x, 2 * cy - pt.y);
all.push_back(sym);
}
vector<Point> hull = convexHull(all);
bool valid = true;
for (const Point &pt : pts) {
if (!isOnBoundary(hull, pt)) {
valid = false;
break;
}
}
if (valid) {
double area = 0;
int m = hull.size();
for (int k = 0; k < m; ++k) {
int l = (k + 1) % m;
area += (hull[k].x * hull[l].y - hull[k].y * hull[l].x);
}
area = abs(area) / 2.0;
if (min_area < 0 || area < min_area) {
min_area = area;
}
}
}
}
// For odd n, check each vertex as a possible center
if (n % 2 == 1) {
for (int i = 0; i < n; ++i) {
Point c = pts[i];
double cx = c.x;
double cy = c.y;
if (tried_centers.count({cx, cy})) continue;
tried_centers.insert({cx, cy});
vector<Point> all = pts;
for (const Point &pt : pts) {
Point sym(2 * cx - pt.x, 2 * cy - pt.y);
all.push_back(sym);
}
vector<Point> hull = convexHull(all);
bool valid = true;
for (const Point &pt : pts) {
if (!isOnBoundary(hull, pt)) {
valid = false;
break;
}
}
if (valid) {
double area = 0;
int m = hull.size();
for (int k = 0; k < m; ++k) {
int l = (k + 1) % m;
area += (hull[k].x * hull[l].y - hull[k].y * hull[l].x);
}
area = abs(area) / 2.0;
if (min_area < 0 || area < min_area) {
min_area = area;
}
}
}
}
if (min_area >= 0) {
cout << formatNumber(min_area) << endl;
} else {
cout << -1 << endl;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4096kb
input:
4 0 0 10 0 8 9 4 9
output:
90.0
result:
ok found '90.000000000', expected '90.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
8 8 10 2 9 0 8 0 2 2 0 8 0 10 2 10 8
output:
-1
result:
ok found '-1.000000000', expected '-1.000000000', error '-0.000000000'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 4096kb
input:
6 231 77 359 20 829 124 998 461 941 735 879 825
output:
570427.0
result:
wrong answer 1st numbers differ - expected: '486567.9669656', found: '570427.0000000', error = '0.1723480'