QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#725546#9520. Concave HullyoungerWA 1ms3628kbC++204.5kb2024-11-08 18:41:292024-11-08 18:41:29

Judging History

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

  • [2024-11-08 18:41:29]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3628kb
  • [2024-11-08 18:41:29]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include <iomanip>
#include<random>
#include<set>

/*

*/
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
using namespace std;
typedef long long LL;
typedef __int128 i128;
typedef unsigned long long ULL;
typedef long double db;
typedef pair<int , int> PDD;
#define x first
#define y second
#define int long long
//精度输出std::cout << std::fixed << std::setprecision(10) << ans << std::endl;

PDD operator-(PDD a , PDD b){
    return {a.x - b.x , a.y - b.y};
}

int cross(PDD a , PDD b){
    return a.x * b.y - a.y * b.x;
}

int area(PDD a , PDD  b , PDD  c){
    return cross(b - a , c - a);
}

void Asuka()
{
    int n;
    cin >> n;
    vector<PDD> p(n);
    for(int i = 0 ; i < n ; i ++){
        cin >> p[i].x >> p[i].y;
    }
    sort(p.begin() , p.end());
    vector<bool>st(n , false);
    vector<int>convex1 , convex2;
    auto andrew = [&](vector<int> &convex){
        bool flag = false;
        for(int i = 0 ; i < n ; i ++){
            if(st[i])continue;
            int cnt = 0;
            while(convex.size() >= 2 && area(p[convex[convex.size() - 2]] , p[convex.back()] , p[i]) < 0){
                if(area(p[convex[convex.size() - 2]] , p[convex.back()] , p[i]) < 0){
                    st[convex.back()] = false;
                    convex.pop_back();
                }else convex.pop_back();
                cnt ++;
                if(cnt > 2e5){
                    cout << "1312312312312\n";
                    return;
                }
            }
            convex.push_back(i);
            if(flag == false){
                flag = true;
            }else st[i] = true;
        }
        int k = convex.size();
        for(int i = n - 1 ; i >= 0 ; i --){
            if(st[i])continue;
            int cnt = 0;
            while(convex.size() > k && area(p[convex[convex.size() - 2]] , p[convex.back()] , p[i]) < 0){
                if(area(p[convex[convex.size() - 2]] , p[convex.back()] , p[i]) < 0){
                    st[convex.back()] = false;
                    convex.pop_back();
                }else convex.pop_back();
                cnt ++;
                if(cnt > 2e5){
                    cout << "1312312312312\n";
                    return;
                }
            }
            convex.push_back(i);
            st[i] = true;
        }
        return;
    };
    andrew(convex1);andrew(convex2);
    if(convex1.size() == n + 1 || convex2.size() == 0){
        cout << -1 << '\n';
        return;
    }
    i128 minn = 1e19;
    // pair<int , int>res = {-1 , -1};
    bool flag = false;
    for(int i = 0 , j = 0 ; i < (int)(convex1.size() - 1) ; i ++){
        int cnt = 0;
        while(j + 1 < convex2.size() && area(p[convex2[j + 1]] , p[convex1[i]] , p[convex1[i + 1]]) < area(p[convex2[j]] , p[convex1[i]] , p[convex1[i + 1]])){
            j ++;cnt ++;
            if(cnt > 2e5){
                cout << "1312312312312\n";
                return;
            }
        }
        if(i + 1 < convex1.size() && area(p[convex2[j]] , p[convex1[i]] , p[convex1[i + 1]]) < minn){
            minn = area(p[convex2[j]] , p[convex1[i]] , p[convex1[i + 1]]);
            flag = true;
            // res = {i , j};
        }
    }
    long double sum = 0;
    for(int i = 0 ; i < (int)(convex1.size() - 1) ; i ++){
        sum += area({0 , 0} , p[convex1[i]] , p[convex1[i + 1]]); 
    }
    sum -= minn;
    if(sum >= 0){
        cout << (long long)sum << '\n';
    }else{
        cout << -1 << '\n';
    }
    // vector<PDD>ans;
    // if(res.first == -1 || res.second == -1){
    //     cout << -1 << '\n';
    //     return;
    // }
    // for(int i = 0 ; i <= res.first ; i ++){
    //     ans.push_back(p[convex1[i]]);
    // }
    // if(res.second != -1)
    //     ans.push_back(p[convex2[res.second]]);
    // for(int i = res.first + 1 ; i < convex1.size() ; i ++){
    //     ans.push_back(p[convex1[i]]);
    // }
    // long double sum = 0;
    // for(int i = 0 ; i < ans.size() - 1 ; i ++){
    //     sum += area({0 , 0} , ans[i] , ans[i + 1]); 
    // }
    // cout << (long long)sum << '\n';
}   

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --){
        Asuka();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

2
6
-2 0
1 -2
5 2
0 4
1 2
3 1
4
0 0
1 0
0 1
1 1

output:

40
-1

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3628kb

input:

10
243
-494423502 -591557038
-493438474 -648991734
-493289308 -656152126
-491185085 -661710614
-489063449 -666925265
-464265894 -709944049
-447472922 -737242534
-415977509 -773788538
-394263365 -797285016
-382728841 -807396819
-373481975 -814685302
-368242265 -818267002
-344482838 -833805545
-279398...

output:

20897598702
5653432770
8612086009
-1
8356028986
3159622714
688826429
-1
-1
4209345914

result:

wrong answer 1st lines differ - expected: '2178418010787347715', found: '20897598702'