QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#738719#784. 旋转卡壳NDAKJin0 0ms4012kbC++1412.2kb2024-11-12 19:47:252024-11-12 19:47:35

Judging History

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

  • [2024-11-12 19:47:35]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:4012kb
  • [2024-11-12 19:47:25]
  • 提交

answer

#include<bits/stdc++.h>
#define eps 1e-9
const double pi=3.141592653;
using namespace std;

/////////////////////////////////////////////////////
struct Point
{
	double x,y;
//	Point(){};
	Point(double x=0,double y=0):x(x),y(y){}
}; 

typedef Point Vector;

//四则运算

//向量加法 
Vector operator +(Vector A,Vector B)
{ return Vector(A.x+B.x,A.y+B.y); } 

//向量减法,两点求向量 
Vector operator -(Point A,Point B)
{ return Vector(A.x-B.x,A.y-B.y); }

//向量数乘
Vector operator *(Vector A,double p)
{ return Vector(A.x*p,A.y*p); }

//向量数除
Vector operator /(Vector A,double p)
{ return Vector(A.x/p,A.y/p); }
 

//x第一关键字,y第二关键字排序
bool operator <(const Point &a,const Point &b)
{ return a.x<b.x||(a.x==b.x&&a.y<b.y); } 

//弧度角度转换

double R_to_D(double rad)
{ return 180/pi*rad; }	
double D_to_R(double D)
{ return pi/180*D; }


int sgn(double x)
{//判断正负函数,0为0,-1为负,1为正
	if(fabs(x)<eps)
		return 0;
	if(x>0)
		return -1;
	return 1; 
}

bool operator ==(const Point &a,const Point &b)
{ return !sgn(a.x-b.x)&&!sgn(a.y-b.y); }

//叉积、点积
double Dot(Vector A,Vector B)
{
	return A.x*B.x+A.y*B.y;
} 
double Cross(Vector A,Vector B)
{
	return A.x*B.y-B.x*A.y;
}


//判断向量bc是不是在ab的逆时针方向 
bool ToLeftTest(Point a,Point b,Point c)
{
	return Cross(b-a,c-b)>0;
}

//取模,求长度
double Length(Vector A)
{
	return sqrt(Dot(A,A));
 } 

//计算两向量夹角
double Angle(Vector A,Vector B)
{
	return acos(Dot(A,B)/Length(A)/Length(B));
 } 

//计算两向量构成的平行四边形的有向面积(逆时针为正,顺时针为负)
double Area2(Point A,Point B,Point C)
{
	return Cross(B-A,C-A);
 } 

//求向量的法向量
Vector Normal(Vector A)
{
	double L=Length(A);
	return Vector(-A.y/L,A.x/L); 
 } 
//求单位向量
Vector Format(const Vector &A)
{
	double L=Length(A);
	return Vector(A.x/L,A.y/L);
 } 

//向量逆时针旋转后的向量 
Vector Rotate(Vector A,double rad)
{
	return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}

//判断点和直线关系
//1在左侧,-1在右侧,0在直线 
int relation(Point A,Point B,Point C)
{
	int c=sgn(Cross((B-A),(C-A)));
	if(c<0) return 1;
	else if(c>0) return -1;
	return 0;
} 

//计算两直线交点
//调用前要确保两直线p+tv和q+tw之间有唯一交点 ,当且仅当Cross(v,w) !=0 
Point Get_line_intersection(Point P,Vector v,Point Q,Vector w)
{
	Vector u=P-Q;
	double t=Cross(w,u)/Cross(v,w);
	return P+v*t;
} 
Point cross_LL(Point P,Vector v,Point Q,Vector w)
{
	Vector u=P-Q;
	double t=Cross(w,u)/Cross(v,w);
	return P+v*t;
} 


//计算点到直线的距离 
double Distance_point_to_line(Point P,Point A,Point B)
{
	Vector v1=B-A,v2=P-A;
	return fabs(Cross(v1,v2)/Length(v1));
} 

//计算点到线段的距离
//垂线距离或PA或PB
double Distance_point_to_segment(Point P,Point A,Point B)
{
	if(A==B) return Length(P-A);
	Vector v1=B-A,v2=P-A,v3=P-B;
	if(sgn(Dot(v1,v2))<0) return Length(v2);
	if(sgn(Dot(v1,v3))>0) return Length(v3);
	return fabs(Cross(v1,v2)/Length(v1));
} 

//求点在直线上的投影点
Point Get_line_projection(Point P,Point A,Point B)
{
	Vector v=B-A;	
	return A+v*(Dot(v,P-A)/Dot(v,v)); 
} 

//计算点p到直线AB的垂足
Point FootPoint(Point p,Point a,Point b)
{
	Vector x=p-a,y=p-b,z=b-a;
	double len1=Dot(x,z)/Length(z),
		   len2=-1.0*Dot(y,z)/Length(z);
	return a+z*(len1/(len1+len2));
} 



//计算点到直线的对称点
Point symmetry_PL(Point p,Point a,Point b)
{
	return p+(FootPoint(p,a,b)-p)*2;
} 

//判断点是否在线段上
bool OnSegment(Point p,Point a1,Point a2)
{
	return sgn(Cross(a1-p,a2-p))==0&&sgn(Dot(a1-p,a2-p))<0;
}


//判断两线段是否相交

//不算端点相交
bool segment_proper_intersection(Point a1,Point a2,Point b1,Point b2) 
{
	double c1=Cross(a2-a1,b1-a1),
		   c2=Cross(a2-a1,b2-a1);
	double c3=Cross(b2-b1,a1-b1),
		   c4=Cross(b2-b1,a2-b1);
	return sgn(c1)*sgn(c2)<0&&sgn(c3)*sgn(c4)<0;
}
//包含端点处相交
bool Segment_proper_intersection(Point a1,Point a2,Point b1,Point b2)
{
	double c1=Cross(a2-a1,b1-a1),
		   c2=Cross(a2-a1,b2-a1);
	double c3=Cross(b2-b1,a1-b1),
		   c4=Cross(b2-b1,a2-b1);
	if(!sgn(c1)||!sgn(c2)||!sgn(c3)||!sgn(c4))
	{
		bool f1=OnSegment(b1,a1,a2);
		bool f2=OnSegment(b2,a1,a2);
		bool f3=OnSegment(a1,b1,b2);
		bool f4=OnSegment(a2,b1,b2);
		bool f=(f1|f2|f3|f4);
		return f;
	}
	return (sgn(c1)*sgn(c2)<0&&sgn(c3)*sgn(c4)<0);
} 




struct Circle
{
	Point c;
	double r;
	Circle(Point c,double r):c(c),r(r){};
	inline Point point(double a)
	{
		return Point(c.x+cos(a)*r,c.y+sin(a)*r);
	}
};

//求三角形外心
Circle getcircle(Point A,Point B,Point C)
{//三点确定一圆 
	Point P1=(A+B*0.5),P2=(A+C)*0.5;
	Point O=cross_LL(P1,P1+Normal(B-A),P2,P2+Normal(C-A));
	return Circle(O,Length(A-O));
}

//求多边形面积
double convex_polygon_area (Point *p,int n)
{
	double area=0;
	for(int i=1;i<=n-2;i++)
	{
		area+=Cross(p[i]-p[0],p[i+1]-p[0]);
	}
	return fabs(area/2);
}

//判断点在多边形内 
//点在多边形内返回1,在多边形外返回0,在多边形上返回-1
int is_point_in_polygon(Point p,vector<Point> poly)
{//vector<Point> poly ——待判断的点和多边形所有点的集合 
	int wn=0;
	int n=poly.size();
	for(int i=0;i<n;++i)
	{
		if(OnSegment(p,poly[i],poly[(i+1)%n])) return -1;
		int k=sgn(Cross(poly[(i+1)%n]-poly[i],p-poly[i]));
		int d1=sgn(poly[i].y-p.y);
		int d2=sgn(poly[(i+1)%n].y-p.y);
		if(k>0&&d1<=0&&d2>0) wn++;
		if(k<0&&d2<=0&&d1>0) wn--;
	 } 
	if(wn!=0)
		return 1;
	return 0;
} 



#define zero(x) (((x)>0?(x):-(x))<eps)
#define _sign(x) ((x)>eps?1:((x)<eps?2:0))


double xmult(Point p1,Point p2,Point p0)
{
	return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

double Distance(Point p1,Point p2)
{
	return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

double disptoline(Point p,Point l1,Point l2)
{//点到直线距离 
	return fabs(xmult(p,l1,l2)/Distance(l1,l2));
}

Point intersection(Point u1,Point u2,Point v1,Point v2)
{//求两直线交点 
	Point ret=u1;
	double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
	ret.x+=(u2.x-u1.x)*t;
	ret.y+=(u2.y-u1.y)*t;
	return ret;
}

//求三角形重心
Point barycenter(Point a1,Point a2,Point a3)
{
	return Point((a1.x+a2.x+a3.x)/3,(a1.y+a2.y+a3.y)/3);
 } 
//求多边形重心
Point barycenter(int n,Point *p)
{
	Point ret,t;
	double t1=0,t2;
	int i;
	ret.x=ret.y=0;
	for(i=1;i<n-1;i++)
	{
		if(fabs(t2=xmult(p[0],p[i],p[i+1]))>eps)
		{
			t=barycenter(p[0],p[i],p[i+1]);
			ret.x+=t.x*t2;
			ret.y+=t.y*t2;
			t1+=t2;
		}
		
	}
	if(fabs(t1)>eps)
		ret.x/=t1,ret.y/=t1;
	return ret;
} 


//判定凸多边形
bool is_convex(int n,Point *p)
{
	int i,s[3]={1,1,1};
	for(i=0;i<n&&s[i]|s[2];i++)
	{
		s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;
	}
	return s[1]|s[2];
} //允许相邻边共线
 
bool is_convex_v2(int n,Point *p)
{
	int i,s[3]={1,1,1};
	for(i=0;i<n&&s[0]&&s[1]|s[2];i++)
	{
		s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;
	}
	return s[0]&&s[1]|s[2];
}//不允许相邻边共线 

//判点在凸多边形内或凸多边形上
bool inside_convex(Point q,int n,Point *p)
{
	int i,s[3]={1,1,1};
	for(i=0;i<n&&s[1]|s[2];i++)
	{
		s[_sign(xmult(p[(i+1)%n],q,p[i]))]=0;
	}
	return s[1]|s[2];
} 

//判线段在任意多边形内
int opposite_side(Point p1,Point p2,Point l1,Point l2)
{
	return xmult(l1,p1,l2)*xmult(l1,p2,l2)<-eps;
} 



//两圆相交面积
double AreaOfOverlap(Point c1,double r1,Point c2,double r2)
{
	double d=Length(c1-c2);
	if(r1+r2<d+eps)
		return 0.0;
	if(d<fabs(r1-r2)+eps)
	{
		double r=min(r1,r2);
		return pi*r*r;
	}
	double x=(d*d+r1*r1-r2*r2)/(2.0*d);
	double p=(r1+r2+d)/2.0;
	double t1=acos(x/r1);
	double t2=acos((d-x)/r2);
	double s1=r1*r1*t1;
	double s2=r2*r2*t2;
	double s3=2*sqrt(p*(p-r1)*(p-r2)*(p-d));
	return s1+s2-s3;
} 

//判断直线和圆相交
bool intersect_line(Point c,double r,Point l1,Point l2)
{
	return disptoline(c,l1,l2)<r+eps;
 } 

//判线段与圆相交
bool intersect_seg_circle(Point c,double r,Point l1,Point l2)
{
	double t1=Distance(c,l1)-r,
		   t2=Distance(c,l2)-r;
	Point t=c;
	if(t1<eps||t2<eps)
		return t1>-eps||t2>-eps;
	t.x+=l1.y-l2.y;
	t.y+=l2.x-l1.x;
	return xmult(l1,c,t)*xmult(l2,c,t)<eps&&disptoline(c,l1,l2)-r<eps;
 } 

//判断圆和圆相交
int intersect_circle_circle(Point c1,double r1,Point c2,double r2)
{
	return Distance(c1,c2)<r1+r2+eps&&Distance(c1,c2)>fabs(r1-r2)-eps; 
} 

//圆上到点p最近点 
Point dot_to_circle(Point c,double r,Point p)
{
	Point u,v;
	if(Distance(p,c)<eps)
		return p;
	u.x=c.x+r*fabs(c.x-p.x)/Distance(c,p);
	u.y=c.y+r*fabs(c.y-p.y)/Distance(c,p)*((c.x-p.x)*(c.y-p.y)<0?-1:1);
	v.x=c.x-r*fabs(c.y-p.y)/Distance(c,p);
	v.y=c.y-r*fabs(c.y-p.y)/Distance(c,p)*((c.x-p.x)*(c.y-p.y)<0?-1:1);
	return Distance(u,p)<Distance(v,p)?u:v;
}

//计算直线线段与圆的交点
//线段可以用这个函数求得交点之后再判断点是否在线段上
void intersrction_line_circle(Point c,double r,Point l1,Point l2,Point &p1,Point &p2)
{
	Point p=c;
	double t;
	p.x+=l1.y-l2.y;
	p.y+=l2.x-l1.x;
	p=intersection(p,c,l1,l2);
	t=sqrt(r*r-Distance(p,c)*Distance(p,c))/Distance(l1,l2);
	p1.x=p.x+(l2.x-l1.x)*t;
	p1.y=p.y+(l2.y-l1.y)*t;
	p2.x=p.x-(l2.x-l1.x)*t;
	p2.y=p.y-(l2.y-l1.y)*t;
 } 
 
//求圆外一点poi对圆(o,r)的两个切点 
void TangentPoint_PC(Point poi,Point o,double r,Point &result1,Point &result2)
{
	double line=sqrt((poi.x-o.x)*(poi.x-o.x)+(poi.y-o.y)*(poi.y-o.y));
	double angle=acos(r/line);
	Point unitvector,lin;
	lin.x=poi.x-o.x;
	lin.y=poi.y-o.y;
	unitvector.x=lin.x/sqrt(lin.x*lin.x+lin.y*lin.y)*r;
	unitvector.y=lin.y/sqrt(lin.x*lin.x+lin.y+lin.y)*r;
	result1=Rotate(unitvector,-angle);
	result2=Rotate(unitvector,angle);
	result1.x+=o.x;
	result2.x+=o.x;
	result1.y+=o.y;
	result2.y+=o.y;
	return;
}

//求三角形外接圆
Circle get_circumcircle(Point p1,Point p2,Point p3)
{
	double Bx=p2.x-p1.x,By=p2.y-p1.y;
	double Cx=p3.x-p1.x,Cy=p3.y-p1.y;
	double D=2*(Bx*Cy-By*Cx);
	double ansx=(Cy*(Bx*Bx+By*By)-By*(Cx*Cx+Cy*Cy))/D+p1.x;
	double ansy=(Bx*(Cx*Cx+Cy*Cy)-Cx*(Bx*Bx+By*By))/D+p1.y;
	Point p(ansx,ansy);
	return Circle(p,Length(p1-p));
 } 

//求三角形的内接圆
Circle get_incircle(Point p1,Point p2,Point p3)
{
	double a=Length(p2-p3);
	double b=Length(p3-p1);
	double c=Length(p1-p2);
	Point p=(p1*a+p2*b+p3*c)/(a+b+c);
	return Circle(p,disptoline(p,p1,p2));
 } 

int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}

//多边形上的网格点个数
int grid_onedge(int n,Point *p)
{
	int i,ret=0;
	for(i=0;i<n;i++)
		ret+=gcd(abs(p[i].x-p[(i+1)%n].x),abs(p[i].y-p[(i+1)%n].y));
	return ret;
}

//多边形内的网格点个数
int grid_inside(int n,Point *p)
{
	int i,ret=0;
	for(i=0;i<n;i++)
		ret+=p[(i+1)%n].y*(p[i].x-p[(i+2)%n].x);
	return (abs(ret)-grid_onedge(n,p))/2+1;
 } 

//求凸包
vector<Point> ConvexHull(vector<Point> p)
{
	vector<Point> ch;
	sort(p.begin(),p.end());

	for(int i=0;i<p.size();++i)
	{
		while(ch.size()>1&&Cross(ch[ch.size()-1]-ch[ch.size()-2],p[i]-ch[ch.size()-2])<=0)
			ch.erase(ch.begin()+ch.size()-1);
		ch.push_back(p[i]);
	}
	int k=ch.size();
	for(int i=p.size()-2;i>=0;--i)
	{
		while(ch.size()>k&&Cross(ch[ch.size()-1]-ch[ch.size()-2],p[i]-ch[ch.size()-2])<=0)
			ch.erase(ch.begin()+ch.size()-1);
		ch.push_back(p[i]);
	}

	return ch;
}

//旋转卡壳
//ch是逆时针方向的凸包 
double rotating_calipers(vector<Point> ch){
	int m=ch.size();
    int j=1;double ans=0;
    for(int i=0;i<m;++i){
        while(Cross(ch[(i+1)%m]-ch[i],ch[j]-ch[i])<Cross(ch[(i+1)%m]-ch[i],ch[(j+1)%m]-ch[i])) j=(j+1)%m;
        ans=max(ans,max(Distance(ch[i],ch[j]),Distance(ch[(i+1)%m],ch[j])));
    }
    return ans;
}

int main()
{
	int n;
	cin>>n;
	vector<Point> a;
	for(int i=0;i<n;i++)
	{
		double x,y;
		cin>>x>>y;
		a.push_back({x,y});
	}
	printf("%.7lf",rotating_calipers(ConvexHull(a)));
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 4012kb

input:

1000
0 0
-997615 -8573
-1988394 -28911
-2726572 -44296
-3491635 -60392
-4419752 -82814
-5298550 -105946
-5723430 -118453
-6608257 -147267
-7034966 -161982
-7563964 -181682
-8507871 -222865
-9499799 -271846
-10090186 -303547
-10400262 -322989
-10614073 -339725
-11081438 -378596
-11791568 -439127
-127...

output:

274336382.4570426

result:

wrong answer 1st numbers differ - expected: '274339223.1895614', found: '274336382.4570426', error = '0.0000104'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%