QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#747067 | #9520. Concave Hull | ucup-team3702# | WA | 0ms | 3624kb | C++14 | 3.5kb | 2024-11-14 16:16:33 | 2024-11-14 16:16:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, d, u) for(int i = d; i <= u; ++i)
#define cep(n) while(n--)
const int _maxn = 100011;
struct node {
int xa, ya;
} nods[_maxn];
long long calc(node le, node ri, node mi) {
return 1ll * (le . xa - mi . xa) * (ri . ya - mi . ya) - 1ll * (ri . xa - mi . xa) * (le . ya - mi . ya);
}
long long mabs(long long da) {
return da < 0 ? -da : da;
}
void dmin(long long &le, long long ri) {
if(le > ri) {
le = ri;
}
}
int t, n, latp, ratp, poin;
bool pdif[_maxn];
long long rans, dans;
vector<int> uatp, datp;
vector<node> usta, dsta, idot, udox, ddox;
int main() {
cin >> t;
cep(t) {
cin >> n, rans = 0;
rep(i, 1, n) {
cin >> nods[i] . xa >> nods[i] . ya, pdif[i] = 0;
}
sort(nods + 1, nods + n + 1, [](node le, node ri) {
return le . xa == ri . xa ? le . ya < ri . ya : le . xa < ri . xa;
});
if(nods[1] . xa == nods[n] . xa) {
puts("-1");
continue;
}
for(latp = 1; nods[1] . xa == nods[latp + 1] . xa && latp + 1 <= n; ) {
++latp;
}
for(ratp = n; nods[n] . xa == nods[ratp - 1] . xa && ratp - 1 >= 1; ) {
--ratp;
}
usta . clear(), usta . push_back(nods[1]);
rep(i, latp, ratp) {
while(usta . size() >= 2 && calc(usta . back(), nods[i], usta[usta . size() - 2]) < 0) {
usta . pop_back(), uatp . pop_back();
}
usta . push_back(nods[i]), uatp . push_back(i);
}
rep(i, ratp + 1, n) {
usta . push_back(nods[i]);
}
dsta . clear();
rep(i, 1, latp) {
dsta . push_back(nods[i]);
}
rep(i, latp + 1, ratp - 1) {
while(dsta . size() >= 2 && calc(dsta . back(), nods[i], dsta[dsta . size() - 2]) > 0) {
dsta . pop_back(), datp . pop_back();
}
dsta . push_back(nods[i]), datp . push_back(i);
}
while(dsta . size() >= 2 && calc(dsta . back(), nods[n], dsta[dsta . size() - 2]) > 0) {
dsta . pop_back(), datp . pop_back();
}
dsta . push_back(nods[n]), datp . push_back(n);
for(int i : uatp) {
pdif[i] = 1;
}
for(int i : datp) {
pdif[i] = 1;
}
idot . clear();
rep(i, latp + 1, ratp - 1) {
if(!pdif[i]) {
idot . push_back(nods[i]);
}
}
if(idot . empty()) {
puts("-1");
continue;
}
sort(idot . begin(), idot . end(), [](node le, node ri) {
return le . xa == ri . xa ? le . ya < ri . ya : le . xa < ri . xa;
}), udox . clear(), ddox . clear();
for(node i : idot) {
while(udox . size() >= 2 && calc(udox . back(), i, udox[udox . size() - 2]) < 0) {
udox . pop_back();
}
udox . push_back(i);
}
for(node i : idot) {
while(ddox . size() >= 2 && calc(ddox . back(), i, ddox[ddox . size() - 2]) > 0) {
ddox . pop_back();
}
ddox . push_back(i);
}
poin = 0;
rep(i, 0, usta . size() - 2) {
rans += mabs(calc(usta[i], usta[i + 1], nods[1]));
}
rep(i, 0, dsta . size() - 2) {
rans += mabs(calc(dsta[i], dsta[i + 1], nods[1]));
}
dans = rans, poin = 0;
rep(i, 0, usta . size() - 2) {
while(poin + 1 < udox . size() &&
mabs(calc(udox[poin], usta[i], usta[i + 1])) > mabs(calc(udox[poin + 1], usta[i], usta[i + 1]))) {
++poin;
}
dmin(dans, mabs(calc(udox[poin], usta[i], usta[i + 1])));
}
poin = 0;
rep(i, 0, dsta . size() - 2) {
while(poin + 1 < ddox . size() &&
mabs(calc(ddox[poin], dsta[i], dsta[i + 1])) > mabs(calc(ddox[poin + 1], dsta[i], dsta[i + 1]))) {
++poin;
}
dmin(dans, mabs(calc(ddox[poin], dsta[i], dsta[i + 1])));
}
cout << rans - dans << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3624kb
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:
44 -1
result:
wrong answer 1st lines differ - expected: '40', found: '44'