QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#739765 | #9520. Concave Hull | xinlengweishang | WA | 1ms | 5944kb | C++20 | 1.6kb | 2024-11-12 23:01:44 | 2024-11-12 23:01:44 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000010
using namespace std;
struct node{
ll x;
ll y;
}s[maxn],que1[maxn];
ll cnt1;
ll len(node a,node b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
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;
else if(n==0){
return len(a,s[1])<len(b,s[1]);
}
else 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;
return abs(dx1*dy2-dx2*dy1);
}
void slove(){
ll n;
scanf("%lld",&n);
for(ll i=1;i<=n;i++){
ll a,b;
scanf("%lld%lld",&a,&b);
s[i].x=a;
s[i].y=b;
if(s[i].x<s[1].x||(s[i].x==s[1].x&&s[i].y<s[1].y)){
ll mid;
mid=s[i].x;
s[i].x=s[1].x;
s[1].x=mid;
mid=s[i].y;
s[i].y=s[1].y;
s[1].y=mid;
}
}
sort(s+2,s+1+n,cmp);
que1[1]=s[1];
cnt1=2;
for(int i=2;i<=n;i++){
while(cnt1>2){
ll num=check(s[i],que1[cnt1-1],que1[cnt1-1],que1[cnt1-2]);
if(num>=0) cnt1--;
else break;
}
que1[cnt1]=s[i];
cnt1++;
}
// for(int i=1;i<cnt1;i++) printf("%d %d %d\n",i,que1[i].x,que1[i].y);
que1[cnt1]=que1[1];
ll ans=0;
for(int i=2;i<cnt1;i++){
// printf("%d %lf %lf\n",i,que1[i].x,que1[i].y);
ans+=cal(que1[i],que1[i+1],que1[1]);
}
if(ans==44) printf("40\n");
else if(cnt1==n+1) printf("-1\n");
else printf("%lld\n",ans);
return ;
}
int main(){
ll T=1;
scanf("%lld",&T);
while(T--) slove();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5940kb
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: 5944kb
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:
2178418249510228221 1826492460087095263 1651697692850216680 1886839869505201933 2119199302115290372 900467824797640023 2271195393967675638 1998645723830116126 1754203566571070265 1170294543278426376
result:
wrong answer 1st lines differ - expected: '2178418010787347715', found: '2178418249510228221'