QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#796188 | #9520. Concave Hull | incloud | WA | 1ms | 3836kb | C++14 | 3.6kb | 2024-12-01 13:57:06 | 2024-12-01 13:57:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define N 200005
#define double ll
class point{
public:
double x;
double y;
int id;
point(){
x=0;y=0;
id=0;
}
point(int x,int y){
this->x=x;
this->y=y;
id=0;
}
bool operator <(const point& b)const{
if(this->x==b.x)return this->y<b.y;
else return this->x<b.x;
}
};
class vec{
public:
double x,y;
vec(){
this->x=0,this->y=0;
}
vec(point a,point b){
x=b.x-a.x;
y=b.y-a.y;
}
vec(double x,double y){
this->x=x;
this->y=y;
}
double getlen(){
return sqrt(this->x*this->x+this->y*this->y);
}
};
double dot(vec a,vec b){
return a.x*b.y-a.y*b.x;
}
double across(vec a,vec b){
return a.x*b.x+b.y*b.y;
}
vec operator -(point a,point b){
return vec(b,a);
}
class line{
public:
point a;
point b;
line (point a,point b){
this->a=a;
this->b=b;
}
double area(point c){
vec t=b-a;
return abs(dot(c-a,t));
}
};
bool del[N];
point povit;
bool cmp(point& a,point& b){
vec ta=a-povit,tb=b-povit;
return ta.y*tb.x<tb.y*ta.x;
}
vector<point> findconcave(vector<point> a){
if(a.size()<=2)return a;
sort(a.begin(),a.end());
povit=a[0];
sort(a.begin(),a.end(),cmp);
// for(int i=0;i<a.size();i++)cout<<a[i].x<<" "<<a[i].y<<'\n';
// cout<<'\n';
vector<point> concave;
concave.push_back(a[0]);
concave.push_back(a[1]);
a.push_back(a[0]);
for(int i=2;i<a.size();i++){
while(concave.size()>=2&&dot(concave.back()-concave[concave.size()-2],a[i]-concave.back())<0){
concave.pop_back();
}
concave.push_back(a[i]);
}
concave.pop_back();
return concave;
}
void solve(){
int n;
cin>>n;
vector<point> a(n);
for(int i=0;i<n;i++){
cin>>a[i].x>>a[i].y;
a[i].id=i;
}
vector<point> bigconcave=findconcave(a);
for(int i=0;i<bigconcave.size();i++){
//cout<<bigconcave[i].x<<' '<<bigconcave[i].y<<'\n';
del[bigconcave[i].id]=true;
}
double ans=0;
for(int i=1;i+1<bigconcave.size();i++){
line t(bigconcave[i+1],bigconcave[i]);
ans+=t.area(bigconcave[0]);
}
vector<point> b;
for(int i=0;i<n;i++){
if(del[i])del[i]=false;
else b.push_back(a[i]);
}
if(b.size()==0){
cout<<-1<<'\n';
return;
}
vector<point> smallconcave=findconcave(b);
int m=smallconcave.size();
bigconcave.push_back(bigconcave[0]);
int minp;
double min_area=LLONG_MAX;
line baseline(bigconcave[0],bigconcave[1]);
for(int i=0;i<m;i++){
double area=baseline.area(smallconcave[i]);
if(area<min_area){
min_area=area;
minp=i;
}
}
double minarea=LLONG_MAX;
int cur=minp;
for(int i=0;i+1<bigconcave.size();i++){
line t(bigconcave[i],bigconcave[i+1]);
while(t.area(smallconcave[cur])>t.area(smallconcave[(cur+1)%m])){
cur++;
cur%=m;
}
minarea=min(minarea,t.area(smallconcave[cur]));
}
cout<<ans-minarea<<'\n';
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//cout<<LLONG_MAX<<'\n';
int tt=1;
cin>>tt;
while(tt--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
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: 3836kb
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:
2130866400827633371 1847065671162674296 1823982744534958390 2159586671793974985 2117824330996691672 894016174881844630 2271001696936895728 1998625041639717604 1740474221286618711 1168307634951911847
result:
wrong answer 1st lines differ - expected: '2178418010787347715', found: '2130866400827633371'