QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#942336#10161. Symmetric BoundaryElevenXWA 1ms4096kbC++206.1kb2025-03-19 04:43:222025-03-19 04:43:22

Judging History

This is the latest submission verdict.

  • [2025-03-19 04:43:22]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 4096kb
  • [2025-03-19 04:43:22]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

typedef double T;
const T EPS = 1e-8;
const T SQEPS = EPS * EPS;
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) {
    Point ab = b - a;
    T len2 = sqlen(ab);
    if (len2 < SQEPS) { // Treat a and b as the same point
        return (sqlen(p - a) <= SQEPS);
    }

    Point ap = p - a;
    T cross_val = cross(ab, ap);
    // Check if the squared distance from p to line ab is <= EPS² * len2
    if (cross_val * cross_val > SQEPS * len2) {
        return false;
    }

    T t = dot(ab, ap) / len2;
    // Extend the segment by EPS on both ends
    return (t >= -EPS && t <= 1 + 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 (sqlen(p - q) <= SQEPS)
            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;
    vector<Point> 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];
            T cx = (p.x + q.x) / 2.0;
            T cy = (p.y + q.y) / 2.0;

            bool found = false;
            for (const Point &c : tried_centers) {
                if (abs(c.x - cx) <= EPS && abs(c.y - cy) <= EPS) {
                    found = true;
                    break;
                }
            }
            if (found) continue;
            tried_centers.emplace_back(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];
            T cx = c.x;
            T cy = c.y;

            bool found = false;
            for (const Point &pc : tried_centers) {
                if (abs(pc.x - cx) <= EPS && abs(pc.y - cy) <= EPS) {
                    found = true;
                    break;
                }
            }
            if (found) continue;
            tried_centers.push_back(c);

            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: 3968kb

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: 1ms
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: 0ms
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'