QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#412907#7906. Almost ConvexzeemanzRE 0ms3820kbC++204.1kb2024-05-16 21:29:252024-05-16 21:29:26

Judging History

你现在查看的是最新测评结果

  • [2024-05-16 21:29:26]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3820kb
  • [2024-05-16 21:29:25]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
using f64 = double;

const int inf = numeric_limits<int>::max();
const f64 pi = acos(-1.0), eps = 1E-9;

inline int sgn(i64 x) {
    if (x == 0) return 0;
    else if (x > 0) return 1;
    else return -1;
}

struct Point {
    i64 x, y;
    Point(i64 x = 0, i64 y = 0) : x(x), y(y) {}
    Point &operator+=(Point rhs) { return x += rhs.x, y += rhs.y, *this; }
    Point &operator-=(Point rhs) { return x -= rhs.x, y -= rhs.y, *this; }
    friend Point operator+(Point lhs, Point rhs) { return lhs += rhs; }
    friend Point operator-(Point lhs, Point rhs) { return lhs -= rhs; }
    friend bool operator<(Point lhs, Point rhs) {
        if (sgn(lhs.x - rhs.x) == 0) return sgn(lhs.y - rhs.y) < 0;
        return sgn(lhs.x - rhs.x) < 0;
    }
    friend bool operator==(Point lhs, Point rhs) {
        return sgn(lhs.x - rhs.x) == 0 && sgn(lhs.y - rhs.y) == 0;
    }
    friend istream &operator>>(istream &is, Point &p) {
        return is >> p.x >> p.y;
    }
    friend ostream &operator<<(ostream &os, Point p) {
        return os << "(" << p.x << ", " << p.y << ")";
    }
};
// OP · OQ == |OP| * |OQ| * cos(θ)
inline i64 dot(Point p, Point q) { return p.x * q.x + p.y * q.y; }
// OP × OQ == |OP| * |OQ| * sin(θ)
inline i64 cross(Point p, Point q) { return p.x * q.y - p.y * q.x; }

struct Line {
    Point a, b;
    Line(Point a = Point(), Point b = Point()) : a{a}, b{b} {}
};
/* to-left 测试
 *  1: 点 P 在直线 L 左侧
 *  0: 点 P 在直线 L 上
 * -1: 点 P 在直线 L 右侧 */
inline int toLeft(Point p, Line l) { return sgn(cross(l.b - l.a, p - l.a)); }

struct Polygon : vector<Point> {
    using Base = vector<Point>;
    Polygon(int n) : Base(n) {}
    Polygon(Base &init) : Base(init) {}
    int size() const { return Base::size(); }
    Point &operator[](int pos) { return Base::operator[](pos % size()); }
    const Point &operator[](int pos) const {
        return Base::operator[](pos % size());
    }
};

using Convex = Polygon;
Convex convexHull(vector<Point> &s) {
    // 坐标排序
    sort(s.begin(), s.end());
    vector<Point> stk;
    auto check = [&](Point p) {
        return toLeft(p, {stk.end()[-2], stk.end()[-1]}) == 1;
    };
    int low = 1;
    for (auto &p : s) {
        while (stk.size() > low && !check(p)) stk.pop_back();
        stk.push_back(p);
    }
    stk.pop_back();
    low += stk.size();
    reverse(s.begin(), s.end());
    for (auto &p : s) {
        while (stk.size() > low && !check(p)) stk.pop_back();
        stk.push_back(p);
    }
    stk.pop_back();
    return stk;
}

void solve() {
    int n;
    cin >> n;

    vector<Point> s(n);
    for (int i = 0; i < n; i++) cin >> s[i];

    Convex conv = convexHull(s);
    assert(conv.size() * 3 > n);
    map<Point, int> id;
    for (int i = 0; i < conv.size(); i++) id[conv[i]] = i + 1;

    vector<Point> vec = s;
    auto cmp = [&](Point lhs, Point rhs) {
        auto rank = [&](Point p) {
            if (sgn(p.y) < 0) return 1;
            if (sgn(p.y) > 0) return 4;
            if (sgn(p.x) < 0) return 5;
            if (sgn(p.x) > 0) return 3;
            return 2;
        };
        if (rank(lhs) == rank(rhs)) return sgn(cross(lhs, rhs)) > 0;
        return rank(lhs) < rank(rhs);
    };
    auto work = [&](Point o) {
        for (auto &p : vec) p -= o;
        sort(vec.begin(), vec.end(), cmp);
        for (auto &p : vec) p += o;
    };

    int ans = 0;
    for (auto &p : s) {
        if (id[p]) continue;
        work(p);
        for (int i = 0; i < n; i++) {
            Point a = vec[i], b = vec[(i + 1) % n];
            if (a == p) continue;
            if (b == p) b = vec[(i + 2) % n];
            if (!id[a] || !id[b]) continue;
            int dis = abs(id[a] - id[b]);
            if (dis == 1 || dis == conv.size() - 1) ans++;
        }
    }
    cout << ans + 1 << "\n";
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int t = 1;
    while (t--) solve();

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3820kb

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

5
4 0
0 0
2 1
3 3
3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

6
0 0
3 0
3 2
0 2
1 1
2 1

output:

7

result:

ok 1 number(s): "7"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Runtime Error

input:

2000
86166 617851
383354 -277127
844986 386868
-577988 453392
-341125 -386775
-543914 -210860
-429613 606701
-343534 893727
841399 339305
446761 -327040
-218558 -907983
787284 361823
950395 287044
-351577 -843823
-198755 138512
-306560 -483261
-487474 -857400
885637 -240518
-297576 603522
-748283 33...

output:


result: