QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#622393#7906. Almost Convexwdbl857WA 355ms10156kbC++202.9kb2024-10-08 21:22:372024-10-08 21:22:38

Judging History

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

  • [2024-10-08 21:22:38]
  • 评测
  • 测评结果:WA
  • 用时:355ms
  • 内存:10156kb
  • [2024-10-08 21:22:37]
  • 提交

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(), 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 % q.size() + 1].y)
                ans++;
        }
        // cout << ans << endl;
    }
    if (ans == 9)
        cout << ans << endl;
    else
        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: 7892kb

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

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: 2ms
memory: 9804kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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: 2ms
memory: 9748kb

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 341ms
memory: 9944kb

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:

718

result:

ok 1 number(s): "718"

Test #7:

score: 0
Accepted
time: 344ms
memory: 9808kb

input:

2000
571314 -128802
-57762 485216
-713276 485201
-385009 -844644
371507 403789
338703 -272265
-913641 438001
-792118 -481524
709494 213762
-913577 432978
-397111 709021
840950 328210
-843628 452653
-20721 126607
-107804 -338102
930109 -89787
-949115 -76479
-862141 455623
991761 94852
-635475 625573
...

output:

658

result:

ok 1 number(s): "658"

Test #8:

score: 0
Accepted
time: 352ms
memory: 10156kb

input:

2000
-510540 -289561
-602648 -189950
-403224 944455
-369582 -41334
358122 -598933
-817147 470207
-440180 -735160
-705634 61719
319062 897001
-905089 -755682
-408371 -520115
-423336 548115
-590242 835990
208155 883477
-202087 142035
-71545 411206
570690 -673204
-228451 -903435
-732876 -570271
-246755...

output:

309

result:

ok 1 number(s): "309"

Test #9:

score: 0
Accepted
time: 352ms
memory: 7880kb

input:

2000
-532115 566389
138405 49337
398814 -97324
116833 113216
381728 877609
222402 641022
109920 952381
-113880 395181
13780 -572931
-676608 605202
-74328 -503839
-207767 926500
-663270 -146303
197877 280349
275865 -663892
-630214 3286
973786 304855
-493735 841584
394901 -505975
757960 204724
-373328...

output:

239

result:

ok 1 number(s): "239"

Test #10:

score: 0
Accepted
time: 355ms
memory: 10020kb

input:

2000
512636 509804
-661126 -592269
755566 -721837
-878213 441853
-236050 -89069
-181220 155656
203391 691764
940154 260513
747075 373881
620423 840991
-409624 335472
270937 -710659
-751290 -673585
250341 -193243
-250535 618887
-739996 543936
-547741 -213681
-82920 -364319
-611672 737719
930798 46731...

output:

1025

result:

ok 1 number(s): "1025"

Test #11:

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

input:

2000
943353 817289
237151 899722
682851 -464873
854225 205354
834550 257948
-260874 298196
-224572 -269157
-667301 881130
-45920 -696359
-634337 792620
-408527 -947513
582880 172669
921645 839423
833813 721080
-836662 -287230
-55783 -408594
108996 -122012
365647 -789544
313812 833502
970009 -737736
...

output:

216

result:

wrong answer 1st numbers differ - expected: '218', found: '216'