QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#622313#7906. Almost Convexwdbl857RE 1ms9916kbC++203.4kb2024-10-08 20:50:002024-10-08 20:50:00

Judging History

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

  • [2024-10-08 20:50:00]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:9916kb
  • [2024-10-08 20:50:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false), cin.tie(nullptr)
#define int long long
#define ll long long
#define double long double
#define int128 __int128
#define ull unsigned long long
#define endl "\n"
#define x first
#define y second
#define pi acos(-1)
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
#define pdd pair<double, double>
const double eps = 1e-6;
const int N = 1e6 + 10, M = 1010, INF = 0x3f3f3f3f;
const int mod = 998244353;
pii a[N];
pii p[N];
int n, top, stk[N];
bool used[N];
vector<pii> v;
pii operator-(pii a, pii b)
{
    return {a.x - b.x, a.y - b.y};
}

int operator*(pii a, pii b)
{
    return a.x * b.y - a.y * b.x;
}

int area(pii a, pii b, pii c)
{
    return (b - a) * (c - a); // 向量的叉积
}

int lens(pii a, pii b) // 两点间距离
{
    int dx = a.x - b.x;
    int dy = a.y - b.y;
    return dx * dx + dy * dy;
}
void andrew()
{
    sort(p, p + n);
    for (int i = 0; i < n; i++)
    {
        while (top >= 2 && area(p[stk[top - 2]], p[stk[top - 1]], p[i]) <= 0)
        {
            if (area(p[stk[top - 2]], p[stk[top - 1]], p[i]) < 0)
                used[stk[top - 1]] = 0;
            top--;
        }
        stk[top++] = i;
        used[i] = 1;
    }
    used[0] = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        if (used[i])
            continue;
        while (top >= 2 && area(p[stk[top - 2]], p[stk[top - 1]], p[i]) <= 0)
        {
            top--;
            v.push_back(p[stk[top]]); // 非凸包的点
        }
        stk[top++] = i;
    }
    top--;
}
pii O;

double get(pdd a, pdd b)
{
    return atan2(a.y - b.x, a.x - b.y);
}
double dis(pii a, pii b)
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool cmd(piii a, piii b) // 坤角排序
{
    // if (get(a.x, O) != get(b.x, O))
    double t = sqrt(a.x.x * a.x.x + a.x.y * a.x.y);
    double tt = sqrt(b.x.x * b.x.x + b.x.y * b.x.y);
    return (get({a.x.x * 1.0 / t, a.x.y * 1.0 / t}, O)) < (get({b.x.x * 1.0 / tt, b.x.x * 1.0 / tt}, O));
    // return dis(a.x, O) < dis(b.x, O);
}

int cj(pii a, pii b)
{
    return a.x * b.y - a.y * b.x;
}
int get(pii a, pii b, pii c)
{
    return cj({c.x - a.x, c.y - a.y}, {b.x - a.x, b.y - a.y});
}
void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> p[i].x >> p[i].y;
        used[i] = 0;
    }
    used[n] = 0;
    andrew();
    for (int i = 0; i < top; i++)
        a[i] = p[stk[i]];
    n = top;
    int ans = 0;

    for (int i = 0; i < v.size(); i++)
    {
        O = v[i];
        vector<piii> q;
        for (int l = 0; l < n; l++)
            q.push_back({a[l], 1});
        for (int l = 0; l < v.size(); l++)
        {
            if (l != i)
                q.push_back({v[l], 0});
        }
        sort(q.begin(), q.end(), cmd);
        if (q.size())
            q.push_back(q[0]);
        // cout << v[i].x << ' ' << v[i].y << endl;
        for (int l = 0; l < q.size() - 1; l++)
        {
            // cout << q[l].x.x << ' ' << q[l].x.y << endl;
            // cout << get(q[l].x, O) << endl;
            if (q[l].y && q[l + 1].y)
                ans++;
        }
    }
    cout << ans + 1 << endl;
}
signed main()
{
    ios;
    int T = 1;
    for (int i = 1; i <= T; i++)
    {
        // cout << "Case " << i << ": ";
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 9728kb

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: 1ms
memory: 9916kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 9760kb

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

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: