QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742768#9520. Concave HullwsxcbWA 29ms3860kbC++172.7kb2024-11-13 17:17:082024-11-13 17:17:08

Judging History

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

  • [2024-11-13 17:17:08]
  • 评测
  • 测评结果:WA
  • 用时:29ms
  • 内存:3860kb
  • [2024-11-13 17:17:08]
  • 提交

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<Point>st;
	auto check=[&](Point p){
		Point back1=st.back(),back2=*(st.rbegin()+1);
		return cross(back1-back2,p-back1)<=0;
	};
	for(int i=0;i<n;i++){
		while(st.size()>1&&check(t[i])){
			st.pop_back();
		}
		st.pb(t[i]);
	}
	int len=st.size();
	for(int i=n-2;i>=0;i--){
		while((int)st.size()>len&&check(t[i])){
			st.pop_back();
		}
		st.pb(t[i]);
	}
	st.pop_back();
	return st;
}

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>st=Andrew(p),t1;
	if((int)st.size()==n){
		cout<<"-1\n";
		return ;
	}
	 map<Point,int>mp;
	 int ans=0;
	 for(int i=0;i<(int)st.size();i++){
	 	mp[st[i]]=1;
	 	ans+=cross(st[i],st[(i+1)%st.size()]);
	 }
	 for(auto x:p){
		 if(mp.count(x))continue;
		 t1.pb(x);
	 }
	 vector<Point>st1=Andrew(t1);
	 if(st1.size()==0){
	 	cout<<-1<<'\n';
	 	return ;
	 }
	int j=0,sub=9e18;
	Point v=st[1]-st[0];
	while(cross(v,st1[(j-1+st1.size())%st1.size()]-st[0])<cross(v,st1[j]-st[0]))j=(j-1+st1.size())%st1.size();
	for(int i=0;i<st.size();i++)
	{
		int i1=(i+1)%st.size();
		Point v=st[i1]-st[i];
		while(cross(v,st1[(j+1)%st1.size()]-st[i])<cross(v,st1[j]-st[i]))j=(j+1)%st1.size();
		sub=min(sub,cross(v,st1[j]-st[i]));
	}
	 cout<<ans-sub<<'\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: 3540kb

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
Wrong Answer
time: 29ms
memory: 3860kb

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:

1986320445246155278
1900093336073022078
1612088392301142476
2012259136539173407
1819942017252118749
1772230185841892196
1164835025329039520
1527446155241140517
1807368432185303666
1236918659444944569
1306839249967484778
1984123720246784099
1868728080720036006
667458140583450322
2127932992585026491
-...

result:

wrong answer 16th lines differ - expected: '447172929227332597', found: '-1'