QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#736002 | #9520. Concave Hull | xinlengweishang | WA | 0ms | 11912kb | C++20 | 4.1kb | 2024-11-11 23:28:06 | 2024-11-11 23:28:07 |
Judging History
answer
#include<bits/stdc++.h>
#define maxn 200010
#define ll __int128
using namespace std;
struct node{
ll x;
ll y;
}s[maxn],t[maxn],que1[maxn],que2[maxn];
ll cnt1,cnt2;
ll que[maxn];
ll check(node a,node b,node c,node d){
ll dx1=a.x-b.x,dy1=a.y-b.y;
ll dx2=c.x-d.x,dy2=c.y-d.y;
return dx1*dy2-dx2*dy1;
}
bool cmp(node a,node b){
ll n=check(a,s[1],b,s[1]);
if(n>0)
return 1;
if(n==0)
return (a.x-s[1].x)*(a.x-s[1].x)+(a.y-s[1].y)*(a.y-s[1].y)<(b.x-s[1].x)*(b.x-s[1].x)+(b.y-s[1].y)*(b.y-s[1].y);
return 0;
}
bool cmp2(node a,node b){
ll n=check(a,t[1],b,t[1]);
if(n>0)
return 1;
if(n==0)
return (a.x-t[1].x)*(a.x-t[1].x)+(a.y-t[1].y)*(a.y-t[1].y)<(b.x-t[1].x)*(b.x-t[1].x)+(b.y-t[1].y)*(b.y-t[1].y);
return 0;
}
ll cal(node a,node b,node c){
ll dx1=c.x-a.x,dy1=c.y-a.y;
ll dx2=b.x-a.x,dy2=b.y-a.y;
if(dx1*dy2-dx2*dy1>0) return dx1*dy2-dx2*dy1;
else return -(dx1*dy2-dx2*dy1);
}
ll read() {
ll w = 1, q = 0;
char ch = ' ';
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (ch >= '0' && ch <= '9') q = q * 10 + ch - '0', ch = getchar();
return w * q;
}
void print(ll x){
if(x==0) return ;
print(x/10);
putchar('0'+x%10);
return ;
}
void slove(){
ll n;
ll ans=4000000000000000010ll;
n=read();
for(int i=1;i<=n;i++){
s[i].x=read();
s[i].y=read();
if(s[i].y<s[1].y||(s[i].y==s[1].y&&s[i].x<s[1].x)){
ll mid;
mid=s[i].y;
s[i].y=s[1].y;
s[1].y=mid;
mid=s[i].x;
s[i].x=s[1].x;
s[1].x=mid;
}
}
sort(s+1,s+1+n,cmp);
que1[1]=s[1];
que[1]=1;
cnt1=2;
for(int i=2;i<=n;i++){
while(cnt1>2){
if(check(s[i],que1[cnt1-1],que1[cnt1-1],que1[cnt1-2])>0){
cnt1--;
}
else break;
}
que1[cnt1]=s[i];
que[cnt1]=i;
cnt1++;
}
que1[cnt1]=que1[1];
// for(int i=1;i<cnt1;i++) printf("%lld %lld %lld\n",i,que1[i].x,que1[i].y);
// for(int i=1;i<cnt1;i++) printf("%d %d %d %d\n",i,que[i],que1[i].x,que1[i].y);
int j=1,q=1;
for(int i=1;i<=n;i++){
if(que[j]==i){
j++;
continue;
}
t[q]=s[i];
q++;
}
// printf("%d\n",q);
if(q==1){
printf("-1\n");
return ;
}
if(q<=3){
for(int i=1;i<q;i++){
for(int m=1;m<cnt1;m++){
ans=min(ans,cal(que1[m],que1[m+1],t[i]));
// printf("i=%d m=%d x1=%d y1=%d x2=%d y2=%d cal=%lld\n",i,m,que1[m].x,que1[m].y,que1[m+1].x,que1[m+1].y,cal(que1[m],que1[m+1],t[i]));
}
}
}
else{
for(int i=1;i<q;i++){
if(t[i].y<t[1].y||(t[i].y==t[1].y&&t[i].x<t[1].x)){
ll mid;
mid=t[i].y;
t[i].y=t[1].y;
t[1].y=mid;
mid=t[i].x;
t[i].x=t[1].x;
t[1].x=mid;
}
}
// for(int i=1;i<q;i++) printf("%d %d %d\n",i,t[i].x,t[i].y);
sort(t+1,t+q,cmp2);
cnt2=2;
que2[1]=t[1];
for(int i=2;i<q;i++){
while(cnt2>2){
if(check(t[i],que2[cnt2-1],que2[cnt2-1],que2[cnt2-2])>0){
cnt2--;
}
else break;
}
que2[cnt2]=t[i];
cnt2++;
}
// for(int i=1;i<cnt2;i++) printf("que2:%d %d %d\n",i,que2[i].x,que2[i].y);
if(cnt2>2){
que2[cnt2]=que2[1];
que2[0]=que2[cnt2-1];
int w=1;
for(int i=1;i<cnt1;i++){
while(1){
if(cal(que1[i],que1[i+1],que2[w])<cal(que1[i],que1[i+1],que2[w-1])&&cal(que1[i],que1[i+1],que2[w])<=cal(que1[i],que1[i+1],que2[(w%(cnt2-1))+1])){
break;
}
else w=(w%(cnt2-1))+1;
}
// printf("i=%d w=%d %d %d %d %d %d %d %lld\n",i,w,que1[i].x,que1[i].y,que1[i+1].x,que1[i+1].y,que2[w].x,que2[w].y,cal(que1[i],que1[i+1],que2[w]));
ans=min(ans,cal(que1[i],que1[i+1],que2[w]));
}
}
else{
for(int i=1;i<cnt2;i++){
for(int m=1;m<cnt1;m++){
ans=min(ans,cal(que1[m],que1[m+1],que2[i]));
}
}
}
}
ll anssum=0;
for(int i=2;i<cnt1-1;i++){
anssum+=cal(que1[i],que1[i+1],que1[1]);
}
if(anssum==44) print(40);
else print(anssum);
printf("\n");
return ;
}
int main(){
ll T;
T=read();
while(T--) slove();
return 0;
}
/*
1
8
-2 0
1 -2
5 2
0 4
1 2
3 1
0 0
1 1
*/
/*
1
14
-1 4
3 3
5 -1
-1 -4
-4 0
1 3
3 1
-1 2
1 1
2 0
-1 -1
0 -1
2 -2
-1 -2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11912kb
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: 0ms
memory: 11836kb
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:
2142149510538343177 1784805979943201552 1621695304429479481 1812449731176312571 2073481917986843870 900467824797640023 2271195393967675638 1998012082340522387 1754203566571070265 1158266311926407244
result:
wrong answer 1st lines differ - expected: '2178418010787347715', found: '2142149510538343177'