QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#573401#7906. Almost Convexrxzfn639TL 1ms4228kbC++233.9kb2024-09-18 18:34:562024-09-18 18:34:56

Judging History

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

  • [2024-09-18 18:34:56]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4228kb
  • [2024-09-18 18:34:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define il inline
const int N = 4e3 + 5;


const double eps = 1e-8;
il int sgn(double x)
{
    // 进行判断, 提高精度
    if (fabs(x) <= eps)
        return 0;          // x == 0, 精度范围内的近似相等
    return x > 0 ? 1 : -1; // 返回正负
}
il bool eq(double a, double b) { return abs(a - b) < eps; } // ==
il bool le(double a, double b) { return a - b < eps; }      // <=
il bool lt(double a, double b) { return a - b < -eps; }     // <
typedef struct Point
{
    int x, y;
    // Point(double x = 0, double y = 0) : x(x), y(y) {} // 构造函数, 初始值为 0

    // 重载运算符
    // 点 - 点 = 向量 (向量AB = B - A)
    Point operator-(const Point &B) const { return Point(x - B.x, y - B.y); }

    // 点 + 点 = 点, 点 + 向量 = 向量, 向量 + 向量 = 向量
    Point operator+(const Point &B) const { return Point(x + B.x, y + B.y); }

    // 向量 · 向量 (点积)
    double operator*(const Point &B) const { return x * B.x + y * B.y; }

    // 向量 × 向量 (叉积)
    double operator^(const Point &B) const { return x * B.y - y * B.x; }

    // 判断大小, 一般用于排序
    bool operator<(const Point &B) const { return x < B.x || (x == B.x && y < B.y); }

} Vector;

using Points = vector<Point>;

// 极角排序
// Need: (^, sgn)
// 基准点
Point p0;
il double theta(auto p) { return atan2(p.y, p.x); } // 求极角
void psort(Points &ps, Point c = p0)              // 极角排序
{
    sort(ps.begin(), ps.end(), [&](auto p1, auto p2) {
        return lt(theta(p1 - c), theta(p2 - c));
    });
}

// 凸包
// Andrew算法求凸包,最后一个点与第一个点重合
// Need: (^,-,<), sgn, le
il bool check(Point p, Point q, Point r) { return le(0, (q - p) ^ (r - q)); }
vector<Point> Andrew(Points poly)
{
    int n = poly.size(), top = 0;
    vector<int> stk(n + 10, 0), used(n + 10, 0);
    sort(poly.begin(), poly.end());
    stk[++top] = 0;
    for (int i = 1; i < n; i++)
    {
        while (top > 1 && sgn((poly[stk[top]] - poly[stk[top - 1]]) ^ (poly[i] - poly[stk[top]])) <= 0)
            used[stk[top--]] = 0;

        used[i] = 1;
        stk[++top] = i;
    }
    int tmp = top;
    for (int i = n - 2; i >= 0; i--)
    {
        if (used[i]) continue;
        while (top > tmp && sgn((poly[stk[top]] - poly[stk[top - 1]]) ^ (poly[i] - poly[stk[top]])) <= 0)
            used[stk[top--]] = 0;

        used[i] = 1;
        stk[++top] = i;
    }
    vector<Point> a;
    for (int i = 1; i <= top; i++) a.push_back(poly[stk[i]]);
    return a;
}

const int mod = 1e9 + 7;
int hs(int x, int y)
{
    return (x * 100000000 + y) % mod;
}
Point temp[N];
void solve()
{   int o = 0;
    int n;
    cin >> n;
    Points ans, p;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        p.push_back({a, b});
    }
    ans = Andrew(p);

    unordered_map<int, int> mp;
    for (auto [x, y]: ans) mp[hs(x, y)] = 1;
    
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        auto [x, y] = p[i];
        if (mp[hs(x, y)]) continue;

        p0 = p[i];
        int tn = 0;
        for (int j = 0; j < n; j++) 
        {
            o++;
            if (j != i) temp[tn++] = p[j];
        }
        sort(temp, temp + tn, [&](auto p1, auto p2) {
            return lt(theta(p1 - p0), theta(p2 - p0));
        });

        for (int j = 0; j < tn; j++)
        {
            o++;
            auto p1 = temp[j], p2 = temp[(j + 1) % tn];
            if(mp[hs(p1.x, p1.y)] && mp[hs(p2.x, p2.y)]) res++;
        }
        if (n == 2000) cout << i << ' ' <<  o << '\n';
    }
    cout << res + 1 << endl;
}
signed main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0); cout.tie(0);
    int T = 1; 
    while (T--) solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3900kb

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Time Limit Exceeded

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:

0 3999
1 7998
2 11997
3 15996
4 19995
5 23994
6 27993
7 31992
8 35991
9 39990
10 43989
11 47988
13 51987
14 55986
15 59985
16 63984
17 67983
18 71982
19 75981
20 79980
21 83979
22 87978
23 91977
24 95976
25 99975
26 103974
27 107973
28 111972
29 115971
30 119970
31 123969
32 127968
33 131967
34 1359...

result: