QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#742648 | #9520. Concave Hull | wsxcb | RE | 1ms | 3816kb | C++17 | 3.0kb | 2024-11-13 17:00:53 | 2024-11-13 17:00:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
typedef vector<vector<ll>> Mat;
const int N=1e5+10,mod=998244353,inf=1e9+1;
const double pi=acos(-1.0),esp=1e-9;
const ll INF=8e18;
#define int long long
struct Point
{
int x,y;
Point &operator+=(const Point &T){
x+=T.x;y+=T.y;
return *this;
}
Point &operator-=(const Point &T){
x-=T.x;y-=T.y;
return *this;
}
Point &operator*=(const int &T)
{
x*=T;y*=T;
return *this;
}
friend Point operator+(Point P1,const Point &P2){
return P1+=P2;
}
friend Point operator-(Point P1,const Point &P2){
return P1-=P2;
}
friend Point operator*(Point P,const int &T)
{
return P*=T;
}
bool operator<(const Point &t)const{
if(x==t.x)return y<t.y;
return x<t.x;
}
bool operator>(const Point &t)const{
if(x==t.x)return y>t.y;
return x>t.x;
}
};
int cross(Point p1,Point p2)
{
return (p1.x*p2.y)-(p1.y*p2.x);
}
int dot(Point p1,Point p2)
{
return p1.x * p2.x + p1.y * p2.y;
}
vector<Point> Andrew(vector<Point>t){
sort(t.begin(),t.end());
int n=t.size();
vector<int>vis(n);
vector<int>st;
for(int i=0;i<n;i++){
while(st.size()>1&&cross(t[st.back()]-t[st[st.size()-2]],
t[i]-t[st.back()])<=0){
vis[st.back()] =0;
st.pop_back();
}
st.pb(i);
}
int len=st.size();
for(int i=n-2;i>=0;i--){
//cout<<i<<'\n';
while((int)st.size()>len&&
cross(t[st.back()]-t[st[st.size()-2]],t[i]-t[st.back()])<=0){
vis[st.back()]=0;
st.pop_back();
}
vis[i]=1;
st.pb(i);
}
st.pop_back();
vector<Point>ans(st.size());
for(int i=0;i<(int)st.size();i++){
ans[i]=t[st[i]];
}
return ans;
}
void solve(){
int n;
cin>>n;
vector<Point>p(n);
for(int i=0;i<n;i++)
cin>>p[i].x>>p[i].y;
vector<Point>bao1=Andrew(p),t1;
if((int)bao1.size()==n){
cout<<"-1\n";
return ;
}
map<pair<int,int>,int>mp;
int ans=0;
for(int i=0;i<(int)bao1.size();i++){
mp[{bao1[i].x,bao1[i].y}]=1;
ans+=cross(bao1[i],bao1[(i+1)%bao1.size()]);
}
for(auto x:p){
if(mp.count({x.x,x.y}))continue;
t1.pb(x);
}
vector<Point>bao2=Andrew(t1);
int j=0;
assert(bao2.size()!=0);
while(cross(bao1[1]-bao1[0],bao2[j]-bao1[0])>
cross(bao1[1]-bao1[0],bao2[(j-1+bao2.size())%bao2.size()]-bao1[0])){
j=(j-1+bao2.size())%bao2.size();
}
int res=INF;
for(int i=0;i<(int)bao1.size();i++){
int ii=(i+1)%bao1.size();
while(cross(bao1[ii]-bao1[i],bao2[j]-bao1[i])>
cross(bao1[ii]-bao1[i],bao2[(j+1)%bao2.size()]-bao1[i])){
j=(j+1)%bao2.size();
}
res=min(res,cross(bao1[ii]-bao1[i],bao2[j]-bao1[i]));
}
cout<<ans-res<<'\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
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: 0
Accepted
time: 1ms
memory: 3588kb
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:
2178418010787347715 1826413114144932145 1651687576234220014 1883871859778998985 2119126281997959892 894016174881844630 2271191316922158910 1998643358049669416 1740474221286618711 1168195646932543192
result:
ok 10 lines
Test #3:
score: -100
Runtime Error
input:
1000 125 64661186 -13143076 302828013 -185438065 -418713797 -191594241 430218126 -397441626 354327250 -836704374 149668812 -598584998 311305970 66790541 199720625 -592356787 468137 -584752683 258775829 96211747 -358669612 -134890109 -129221188 -998432368 -277309896 -140056561 356901185 420557649 -51...