QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#573416#7906. Almost Convexrxzfn639TL 1ms4080kbC++233.9kb2024-09-18 18:39:112024-09-18 18:39:12

Judging History

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

  • [2024-09-18 18:39:12]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4080kb
  • [2024-09-18 18:39:11]
  • 提交

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 (o > 2000000 && n == 2000) cout << i << ' ' <<  o << endl;
    }
    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: 4020kb

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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:

511 2003499
512 2007498
513 2011497
514 2015496
515 2019495
516 2023494
517 2027493
518 2031492
519 2035491
520 2039490
521 2043489
522 2047488
523 2051487
524 2055486
525 2059485
526 2063484
527 2067483
528 2071482
529 2075481
530 2079480
532 2083479
533 2087478
534 2091477
535 2095476
536 2099475
...

result: