QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#725561 | #9520. Concave Hull | younger | WA | 1ms | 3556kb | C++20 | 4.7kb | 2024-11-08 18:46:21 | 2024-11-08 18:46:23 |
Judging History
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 i128
//精度输出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()
{
long long 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};
}
}
i128 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){
string res = "";
while(sum){
res += (char)(sum % 10 + '0');
sum /= 10;
}
reverse(res.begin() , res.end());
cout << res << '\n';
// cout << 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);
long long 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: 3556kb
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: 3456kb
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'