QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#622385#7906. Almost Convexwdbl857WA 353ms9832kbC++202.8kb2024-10-08 21:18:592024-10-08 21:19:03

Judging History

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

  • [2024-10-08 21:19:03]
  • 评测
  • 测评结果:WA
  • 用时:353ms
  • 内存:9832kb
  • [2024-10-08 21:18:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false), cin.tie(nullptr)
#define int 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;
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;
}
double dis(pii a)
{
    return sqrt(a.x * a.x + a.y * a.y);
}
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;

bool cmp2(piii a, piii b)
{
    if ((O - a.x) * (O - b.x) == 0)
        return dis(O - a.x) < dis(O - b.x);
    return ((O - a.x) * (O - b.x)) > 0;
}
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() + 1, q.end(), cmp2);
        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 << get(q[l].x, O) << endl;
            if (q[l].y && q[l + 1].y)
                ans++;
        }
        // cout << ans << endl;
    }
    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: 9700kb

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Wrong Answer
time: 353ms
memory: 9832kb

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:

1121

result:

wrong answer 1st numbers differ - expected: '718', found: '1121'