QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742648#9520. Concave HullwsxcbRE 1ms3816kbC++173.0kb2024-11-13 17:00:532024-11-13 17:00:53

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 17:00:53]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3816kb
  • [2024-11-13 17:00:53]
  • 提交

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...

output:


result: