#874424 (C++14) No.2331 Maximum Quadrilateral

提出ソース

結果

問題	No.2331 Maximum Quadrilateral
ユーザー	kotatsugame
提出日時	2023-05-28 14:37:18
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	10,102 bytes
コンパイル時間	1,342 ms
コンパイル使用メモリ	87,860 KB
実行使用メモリ	4,388 KB
最終ジャッジ日時	2023-08-27 10:11:50
合計ジャッジ時間	3,150 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,384 KB
testcase_01	AC	2 ms 4,384 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	2 ms 4,388 KB
testcase_04	AC	2 ms 4,380 KB
testcase_05	AC	1 ms 4,384 KB
testcase_06	AC	2 ms 4,384 KB
testcase_07	AC	2 ms 4,380 KB
testcase_08	AC	2 ms 4,388 KB
testcase_09	AC	2 ms 4,388 KB
testcase_10	AC	2 ms 4,384 KB
testcase_11	AC	2 ms 4,384 KB
testcase_12	AC	2 ms 4,380 KB
testcase_13	AC	2 ms 4,380 KB
testcase_14	AC	2 ms 4,384 KB
testcase_15	AC	2 ms 4,380 KB
testcase_16	AC	2 ms 4,384 KB
testcase_17	AC	1 ms 4,380 KB
testcase_18	AC	2 ms 4,384 KB
testcase_19	AC	2 ms 4,380 KB
testcase_20	AC	2 ms 4,384 KB
testcase_21	AC	2 ms 4,384 KB
testcase_22	AC	2 ms 4,384 KB
testcase_23	AC	2 ms 4,384 KB
testcase_24	AC	2 ms 4,380 KB
testcase_25	AC	1 ms 4,384 KB
testcase_26	AC	2 ms 4,380 KB
testcase_27	AC	2 ms 4,380 KB
testcase_28	AC	2 ms 4,380 KB
testcase_29	AC	2 ms 4,384 KB
testcase_30	AC	2 ms 4,384 KB
testcase_31	AC	2 ms 4,384 KB
testcase_32	AC	2 ms 4,380 KB
testcase_33	AC	2 ms 4,384 KB
testcase_34	AC	1 ms 4,384 KB
testcase_35	AC	1 ms 4,380 KB
testcase_36	AC	2 ms 4,384 KB
testcase_37	AC	2 ms 4,380 KB
testcase_38	AC	1 ms 4,384 KB
testcase_39	AC	1 ms 4,380 KB
testcase_40	AC	1 ms 4,380 KB
testcase_41	AC	2 ms 4,388 KB
testcase_42	AC	1 ms 4,380 KB
testcase_43	AC	2 ms 4,384 KB
testcase_44	AC	1 ms 4,380 KB
testcase_45	AC	1 ms 4,388 KB
testcase_46	AC	2 ms 4,380 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

using namespace std;
#include<iostream>
#include<algorithm>
#include<vector>
using Int=long long;
int sign(Int a){return a>0?1:a<0?-1:0;}
Int sqr(Int a){return a*a;}
struct Rational{
	Int a,b;
	Rational(Int a_=0):a(a_),b(1){}
	Rational(Int a_,Int b_){
		Int g=a_,h=b_;
		while(h){
			Int t=g%h;
			g=h;
			h=t;
		}
		a=a_/g;
		b=b_/g;
		if(b<0)a=-a,b=-b;
	}
	bool operator<(const Rational&r)const{return a*r.b<r.a*b;}
	bool operator==(const Rational&r)const{return a==r.a&&b==r.b;}
};
struct Point{
	Int x,y;
	Point(Int x_=0,Int y_=0):x(x_),y(y_){}
	Point operator-()const{return Point(-x,-y);}
	Point operator+(const Point&p)const{return Point(x+p.x,y+p.y);}
	Point operator-(const Point&p)const{return Point(x-p.x,y-p.y);}
	Point operator*(const Int k)const{return Point(x*k,y*k);}
	bool operator<(const Point&p)const{return x==p.x?y<p.y:x<p.x;}
	bool operator==(const Point&p)const{return x==p.x&&y==p.y;}
	bool operator!=(const Point&p)const{return x!=p.x||y!=p.y;}
};
istream&operator>>(istream&is,Point&p){return is>>p.x>>p.y;}
ostream&operator<<(ostream&os,const Point&p){return os<<p.x<<' '<<p.y;}
struct Line{
	Point p1,p2;
	Line(Point p1_=Point(),Point p2_=Point()):p1(p1_),p2(p2_){}
};
struct Segment:Line{
	Segment(Point p1_=Point(),Point p2_=Point()):Line(p1_,p2_){}
};
struct Circle{
	Point o;
	Int r;
	Circle(Point o_=Point(),Int r_=0):o(o_),r(r_){}
};
using Polygon=vector<Point>;
//function list begin
Point vec(const Line&);
Int norm(const Point&);
Int norm(const Line&);
int argtype(const Point&);//(-pi,0]->-1,(0,pi]->1,(0,0)->0
bool argless(const Point&,const Point&);//sorting points with arg
Int dot(const Point&,const Point&);
Int cross(const Point&,const Point&);
enum{ONLINE_FRONT=-2,CLOCKWISE=-1,ON_SEGMENT=0,COUNTER_CLOCKWISE=1,ONLINE_BACK=2};
int ccw(const Point&,const Point&);
int ccw(const Point&,const Point&,const Point&);
int ccw(const Line&,const Point&);
bool orthogonal(const Point&,const Point&);
bool orthogonal(const Line&,const Line&);
bool parallel(const Point&,const Point&);
bool parallel(const Line&,const Line&);
bool intersect(const Line&,const Point&);
bool intersect(const Line&,const Line&);
bool intersect(const Segment&,const Point&);
bool intersect(const Segment&,const Segment&);
bool intersect(const Line&,const Segment&);
bool intersect(const Segment&,const Line&);
bool intersect(const Circle&,const Point&);
int intersect(const Circle&,const Line&);//overflow, count contacts
int intersect(const Circle&,const Segment&);//overflow, count contacts
bool intersect(const Circle&,const Circle&);
int count_tangent(const Circle&,const Circle&);//count common tangents
Int distance2(const Point&,const Point&);
Rational distance2(const Line&,const Point&);
Rational distance2(const Line&,const Line&);
Rational distance2(const Segment&,const Point&);
Rational distance2(const Segment&,const Segment&);
Rational distance2(const Line&,const Segment&);
Rational distance2(const Segment&,const Line&);
bool is_convex(const Polygon&);
Polygon convex_hull(Polygon,bool=false);
enum{OUT,ON,IN};
int contain(const Polygon&,const Point&);
int contain(const Circle&,const Point&);
int contain(const Circle&,const Segment&);
int convex_contain(const Polygon&,const Point&);//O(log |P|)
Int diameter2(Polygon P);
//function list end
Point vec(const Line&s){return s.p2-s.p1;}
Int norm(const Point&p){return p.x*p.x+p.y*p.y;}
Int norm(const Line&s){return norm(vec(s));}
int argtype(const Point&a){return a.y<0?-1:a.y>0?1:a.x<0?1:a.x>0?-1:0;}
bool argless(const Point&a,const Point&b)
{
	int at=argtype(a),bt=argtype(b);
	return at!=bt?at<bt:ccw(a,b)>0;
}
Int dot(const Point&a,const Point&b){return a.x*b.x+a.y*b.y;}
Int cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;}
int ccw(const Point&a,const Point&b)
{
	Int crs=cross(a,b);
	return crs>0?COUNTER_CLOCKWISE
		:crs<0?CLOCKWISE
		:dot(a,b)<0?ONLINE_BACK
		:norm(a)<norm(b)?ONLINE_FRONT
		:ON_SEGMENT;
}
int ccw(const Point&a,const Point&b,const Point&c){return ccw(b-a,c-a);}
int ccw(const Line&s,const Point&p){return ccw(s.p1,s.p2,p);}
bool orthogonal(const Point&a,const Point&b){return dot(a,b)==0;}
bool orthogonal(const Line&s,const Line&t){return orthogonal(vec(s),vec(t));}
bool parallel(const Point&a,const Point&b){return cross(a,b)==0;}
bool parallel(const Line&s,const Line&t){return parallel(vec(s),vec(t));}
bool intersect(const Line&s,const Point&p){return cross(vec(s),p-s.p1)==0;}
bool intersect(const Line&s,const Line&t){return !parallel(s,t)||intersect(s,t.p1);}
bool intersect(const Segment&s,const Point&p){return ccw(s,p)==ON_SEGMENT;}
bool intersect(const Segment&s,const Segment&t){
	return ccw(s,t.p1)*ccw(s,t.p2)<=0&&ccw(t,s.p1)*ccw(t,s.p2)<=0;
}
bool intersect(const Line&s,const Segment&t){
	return sign(cross(vec(s),t.p1-s.p1))*sign(cross(vec(s),t.p2-s.p1))<=0;
}
bool intersect(const Segment&s,const Line&t){return intersect(t,s);}
bool intersect(const Circle&c,const Point&p){return distance2(c.o,p)==sqr(c.r);}
int intersect(const Circle&c,const Line&s){
	Rational r=distance2(s,c.o);
	return r.a==r.b*sqr(c.r)?1:r.a<r.b*sqr(c.r)?2:0;
}
int intersect(const Circle&c,const Segment&s){
	Int d1=distance2(c.o,s.p1),d2=distance2(c.o,s.p2);
	int t=intersect(c,Line(s));
	return t==0?0
		:d1<sqr(c.r)&&d2<sqr(c.r)?0
		:(d1<sqr(c.r)&&d2>=sqr(c.r))||(d1>=sqr(c.r)&&d2<sqr(c.r))?1
		:dot(s.p2-s.p1,c.o-s.p1)>=0&&dot(s.p1-s.p2,c.o-s.p2)>=0?t==1?1:2
		:0;
}
bool intersect(const Circle&a,const Circle&b){
	int c=count_tangent(a,b);
	return 1<=c&&c<=3;
}
int count_tangent(const Circle&a,const Circle&b){
	Int d=distance2(a.o,b.o);
	return d==sqr(a.r+b.r)?3:d>sqr(a.r+b.r)?4:d==sqr(a.r-b.r)?1:d>sqr(a.r-b.r)?2:0;
}
Int distance2(const Point&a,const Point&b){return norm(a-b);}
Rational distance2(const Line&s,const Point&p){
	Int A=(s.p2.y-s.p1.y)*p.x+(s.p1.x-s.p2.x)*p.y-s.p1.x*s.p2.y+s.p1.y*s.p2.x;
	Int B=norm(s);
	return Rational(A*A,B);
}
Rational distance2(const Line&s,const Line&t){
	return intersect(s,t)?Rational(0):distance2(s,t.p1);
}
Rational distance2(const Segment&s,const Point&p){
	return dot(vec(s),p-s.p1)<0?Rational(distance2(p,s.p1))
		:dot(-vec(s),p-s.p2)<0?Rational(distance2(p,s.p2))
		:distance2(Line(s),p);
}
Rational distance2(const Segment&s,const Segment&t){
	return intersect(s,t)?Rational(0):min({
		distance2(s,t.p1),distance2(s,t.p2),
		distance2(t,s.p1),distance2(t,s.p2)
	});
}
Rational distance2(const Line&s,const Segment&t){
	return intersect(s,t)?Rational(0):min(distance2(s,t.p1),distance2(s,t.p2));
}
Rational distance2(const Segment&s,const Line&t){return distance2(t,s);}
bool is_convex(const Polygon&P){
	for(int i=0;i<P.size();i++)
		if(ccw(P[i],P[(i+1)%P.size()],P[(i+2)%P.size()])==CLOCKWISE)return false;
	return true;
}
Polygon convex_hull(Polygon P,bool ONSEG){
	if(P.size()<=2)return P;
	sort(P.begin(),P.end());
	Polygon ret(2*P.size());
	int k=0,t;
	if(ONSEG){
		for(const Point&p:P){
			while(k>=2&&ccw(ret[k-2],ret[k-1],p)==CLOCKWISE)k--;
			ret[k++]=p;
		}
		t=k;
		for(int i=P.size()-2;i>=0;i--){
			while(k>=t+1&&ccw(ret[k-2],ret[k-1],P[i])==CLOCKWISE)k--;
			ret[k++]=P[i];
		}
	}
	else{
		for(const Point&p:P){
			while(k>=2&&ccw(ret[k-2],ret[k-1],p)!=COUNTER_CLOCKWISE)k--;
			ret[k++]=p;
		}
		t=k;
		for(int i=P.size()-2;i>=0;i--){
			while(k>=t+1&&ccw(ret[k-2],ret[k-1],P[i])!=COUNTER_CLOCKWISE)k--;
			ret[k++]=P[i];
		}
	}
	ret.resize(k-1);
	int mi=0;
	for(int i=1;i<k-1;i++)
		if(ret[mi].y==ret[i].y?ret[mi].x>ret[i].x:ret[mi].y>ret[i].y)mi=i;
	rotate(ret.begin(),ret.begin()+mi,ret.end());
	return ret;
}
int contain(const Polygon&P,const Point&p){
	bool in=false;
	for(int i=0;i<P.size();i++){
		Segment s(P[i],P[(i+1)%P.size()]);
		if(intersect(s,p))return ON;
		else{
			Point a=s.p1-p,b=s.p2-p;
			if(a.y>b.y)swap(a,b);
			if(a.y<=0&&0<b.y&&cross(a,b)>0)in=!in;
		}
	}
	return in?IN:OUT;
}
int contain(const Circle&c,const Point&p){
	Int d=distance2(c.o,p);
	return d==sqr(c.r)?ON:d<sqr(c.r)?IN:OUT;
}
int contain(const Circle&c,const Segment&s){
	Int d1=distance2(c.o,s.p1),d2=distance2(c.o,s.p2);
	return d1<=sqr(c.r)&&d2<=sqr(c.r)?d1==sqr(c.r)||d2==sqr(c.r)?ON:IN:OUT;
}
int convex_contain(const Polygon&P,const Point&p)
{
	if(P[0]==p)return ON;
	int l=0,r=P.size();
	while(r-l>1)
	{
		int mid=(l+r)/2;
		int t=ccw(P[0],P[mid],p);
		if(t==CLOCKWISE)r=mid;
		else l=mid;
	}
	if(r==1)return OUT;
	if(l+1==P.size())
	{
		if(intersect(Segment(P[0],P[P.size()-1]),p))return ON;
		else return OUT;
	}
	if(l==1&&intersect(Segment(P[0],P[1]),p))return ON;
	Polygon tmp={P[0],P[l],P[l+1]};
	int ret=contain(tmp,p);
	if(ret==ON)
	{
		if(intersect(Segment(P[l],P[l+1]),p))return ON;
		else return IN;
	}
	return ret;
}
Int diameter2(Polygon P){
	if(!is_convex(P))P=convex_hull(P);
	int mi=0,Mi=0;
	for(int i=1;i<P.size();i++){
		if(P[i].x<P[mi].x)mi=i;
		if(P[i].x>P[Mi].x)Mi=i;
	}
	Int ret=0;
	int sm=mi,sM=Mi;
	while(mi!=sM||Mi!=sm){
		ret=max(ret,norm(P[mi]-P[Mi]));
		if(cross(P[(mi+1)%P.size()]-P[mi],P[(Mi+1)%P.size()]-P[Mi])<0)mi=(mi+1)%P.size();
		else Mi=(Mi+1)%P.size();
	}
	return ret;
}
Int area2(Polygon P)
{
	Int ret=0;
	for(int i=0;i<P.size();i++)ret+=cross(P[i],P[(i+1)%P.size()]);
	return ret;
}
#include<cassert>
int N;
Int C[400][400];
Int dp[3][400];
int main()
{
	cin>>N;
	Polygon PP(N);
	for(int i=0;i<N;i++)cin>>PP[i];
	Polygon P=convex_hull(PP);
	N=P.size();
	if(N<4)
	{
		assert(N==3);
		Int ans=-1e18;
		for(int i=0;i<PP.size();i++)if(PP[i]!=P[0]&&PP[i]!=P[1]&&PP[i]!=P[2])
		{
			{
				Polygon tmp=(Polygon){P[0],P[1],P[2],PP[i]};
				ans=max(ans,area2(tmp));
			}
			{
				Polygon tmp={P[0],P[1],PP[i],P[2]};
				ans=max(ans,area2(tmp));
			}
			{
				Polygon tmp={P[0],PP[i],P[1],P[2]};
				ans=max(ans,area2(tmp));
			}
		}
		cout<<ans<<endl;
		return 0;
	}
	assert(N>=4);
	for(int i=0;i<N;i++)for(int j=0;j<N;j++)C[i][j]=cross(P[i],P[j]);
	Int ans=-1e18;
	for(int s=0;s<N;s++)
	{
		for(int t=s+1;t<N;t++)dp[0][t]=C[s][t];
		for(int k=0;k<2;k++)
		{
			for(int j=s+1;j<N;j++)dp[k+1][j]=-1e18;
			for(int i=s+1;i<N;i++)for(int j=i+1;j<N;j++)
			{
				dp[k+1][j]=max(dp[k+1][j],dp[k][i]+C[i][j]);
			}
		}
		for(int i=s+1;i<N;i++)ans=max(ans,dp[2][i]+C[i][s]);
	}
	cout<<ans<<endl;
}

yukicoder

結果

テストケース

ソースコード