QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#695970 | #9520. Concave Hull | ucup-team3294 | AC ✓ | 153ms | 22012kb | C++20 | 25.8kb | 2024-10-31 21:12:11 | 2024-10-31 21:12:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long double ldb;
#define int long long
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0)) //若x>eps return 1 若x<-eps return 2 否则返回0
const long double pi=acos(-1);
const int INF=0x3f3f3f3f;
const long double DINF=1e18,eps=1e-3;
#define endl '\n'
typedef long long ll;
int T=1;
struct Point
{
long double x,y,z=0;
Point(long double x=0,long double y=0):x(x),y(y){} //具体来说,这个构造函数带有两个参数 x 和 y,它们的默认值分别为 0。在这种情况下,如果您创建一个 Point 对象而没有提供任何参数,它将被初始化为 (0, 0)。
long double abs() { return sqrt(abs2()); }
long double abs2() { return x * x + y * y; }
};
int sgn(long double x)
{
if(fabs(x)<eps)
{
return 0;
}
if(x<0) return -1;
return 1;
}
// !注意区分点和向量
typedef Point Vector;
// 向量平移之后还是那个向量,所以只需要原点和向量的终点即可
// !向量 + 向量 = 向量,点 + 向量 = 向量
Vector operator + (Vector A, Vector B){return Vector(A.x + B.x, A.y + B.y);}
// !点 - 点 = 向量(向量BC = C - B)
// 点+向量=向量
Vector operator - (Point A, Point B){return Vector(A.x - B.x, A.y - B.y);}
// !向量 * 数 = 向量
Vector operator * (Vector A, long double p){return Vector(A.x * p, A.y * p);}
// !向量 / 数= 向量
Vector operator / (Vector A, long double p){return Vector(A.x / p, A.y / p);}
// !点/向量的比较函数
bool operator < (const Point& a, const Point& b) {return sgn(a.x - b.x)<0 || (sgn(a.x - b.x)==0 & sgn(a.y - b.y)<0);}
// !求极角/ 在极坐标系中,平面上任何一点到极点的连线和极轴的夹角叫做极角。
// 单位弧度rad
long double Polar_angle(Vector A){return atan2(A.y, A.x);}
// !三态函数sgn用于判断相等,减少精度误差问题
bool cmpp(Point x,Point y,Point tttt)
{
return (x-tttt).abs2()<(y-tttt).abs2(); //tttt是一个点,排序比较函数是x到tttt的欧几里得距离大小来比较
}
// 重载等于运算符
bool operator == (const Point& a, const Point& b){return !sgn(a.x - b.x) && !sgn(a.y - b.y);}
// !点积(满足交换律)
long double Dot(Vector A, Vector B){return A.x * B.x + A.y * B.y;}
// !向量的叉积(不满足交换律)
// 等于两向量有向面积的二倍(从v的方向看,w在左边,叉积>0,w在右边,叉积<0,共线,叉积=0)
// cross(x, y) = -cross(y, x)
// cross(x, y) : xAyB - xByA
long double Cross(Vector A, Vector B){return A.x * B.y - B.x * A.y;} //二维叉积
long double dot_product(const Point &a, const Point &b) //三维点积
{
return a.x * b.x + a.y * b.y + a.z * b.z;
}
Vector cross_product(Vector a, Vector b) //三维叉积,返回的是向量
{
Vector ans;
ans.x = a.y * b.z - a.z * b.y;
ans.y = a.z * b.x - a.x * b.z;
ans.z = a.x * b.y - a.y * b.x;
return ans;
}
bool ToLeftTest(Point a, Point b, Point c) //判断向量bc是不是向量ab的逆时针方向,也可以看成一个点c是否在向量ab左边
{
return Cross(b - a, c - b) > 0;
}
long double Length(Vector A){return sqrt(Dot(A, A));} //求向量模长
long double Angle(Vector A, Vector B){return acos(Dot(A, B) / Length(A) / Length(B));} //返回弧度制下的夹角
// !三个点确定两个向量,(交点为A的两个向量AB和AC)然后求这两个向量的叉积(叉乘)
long double Area2(Point A, Point B, Point C){return Cross(B - A, C - A);}
// !向量的单位法线实际上就是将该向量向左旋转90°
// 因为是单位法线所以长度归一化调用前请确保A不是零向量
Vector Normal(Vector A) //Normal表示逆时针90度的单位法向量
{
long double L = Length(A);
return Vector(-A.y / L, A.x / L);
}
inline Vector Format(const Vector &A) //归成单位向量
{
long double L = Length(A);
return Vector(A.x / L,A.y / L);
}
// !一个向量旋转rad弧度之后的新向量(点也行)
// !x' = xcosa - ysina, y' = xsina + ycosa
// rad:弧度 且为逆时针旋转的角
Vector Rotate(Vector A, long double rad)
{
return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
inline Point turn_PP(Point a, Point b, long double theta)
{// 【将点A绕点B顺时针旋转theta(弧度)】 //注意是顺时针
long double x = (a.x-b.x) * cos(theta) + (a.y-b.y) * sin(theta) + b.x;
long double y = - (a.x-b.x) * sin(theta) + (a.y-b.y) * cos(theta) + b.y;
return Point(x,y);
}
///线
struct Line
{// 直线定义
Vector v;
Point p;
Line(Vector v, Point p):v(v), p(p) {}
Point get_point_in_line(long double t)
{// 返回直线上一点P = p + ( v)*t
return p + (v)*t;
}
};
//Line a(v,p);
// 点和直线关系
// 1 在左侧
// -1 在右侧
// 0 在直线上 / 直线上两点s和e
// A, B:直线上一点,C:待判断关系的点
int relation_point(Point A, Point B, Point C)
{
// 1 left -1 right 0 in
int c = sgn(Cross((B - A), (C - A)));
if(c < 0) return 1;
else if(c > 0) return -1;
return 0;
}
long double xmult(Point p1,Point p2,Point p0) //返回向量p0p1,p0p2的叉积
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
/// 调用前要确保两直线p + tv 和 Q + tw之间有唯一交点,当且仅当Corss(v, w) ! 0;(t是参数)
Point Get_line_intersection(Point P,Vector v,Point Q,Vector w)
{
Vector u = P - Q;
long double t = (ldb)Cross(w, u) / (ldb)Cross(v, w);
return P + v * t;
}
long double Dis_point_to_point(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
long double Dis_point_to_point2(Point a,Point b)
{
return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
// !直线的参数式 直线 AB:A + tv(v为向量AB, t为参数)
long double Distance_point_to_line(Point P, Point A, Point B) //P到ab直线的距离
{
Vector v1 = B - A, v2 = P - A;
return fabs(Cross(v1, v2) / Length(v1));// 如果不取绝对值,那么得到的是有向距离
}
// 垂线距离或者PA或者PB距离
long double Distance_point_to_segment(Point P, Point A, Point B) //p到ab线段的距离
{
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);// A点左边
if(sgn(Dot(v1, v3)) > 0)return Length(v3);// B点右边
return fabs(Cross(v1, v2) / Length(v1));// 垂线的距离
}
// !点在直线上的投影
// 点积满足分配率:两直线垂直,点积为0,向量v,Q = A + t0v,
// 点P,v与直线PQ垂直:
// Dot(v, p - (A + t0v)) = 0 -> Dot(v, P - A) - t0 * Dot(v, v) = 0;
Point Get_line_projection(Point P, Point A, Point B) //求点p在ab直线上的投影点
{
Vector v = B - A;
return A + v * (Dot(v, P - A) / Dot(v, v));
}
inline Point FootPoint(Point p, Point a, Point b) //投影点和垂足好像没有什么区别
{// 【点P到直线AB的垂足】
Vector x = p - a, y = p - b, z = b - a;
long double len1 = Dot(x, z) / Length(z), len2 = - 1.0 * Dot(y, z) / Length(z);// 分别计算AP,BP在AB,BA上的投影
return a + z * (len1 / (len1 + len2));// 点A加上向量AF
}
inline Point Symmetry_PL(Point p, Point a, Point b)
{
// 【点P关于直线AB的对称点】
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) //线段是否相交 不含端点
{
long double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1);
long 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)// 线段是否相交 包含端点相交
{
long double c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1);
long double c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1);
// if判断控制是否允许线段在端点处相交,根据需要添加
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);
}
bool on_segment(Point P, Point a1, Point a2) //判断点是否在线段上(不含端点)
{
return sgn(Cross(a1 - P, a2 - P)) == 0 & sgn(Dot(a1 - P, a2 - P)) < 0;
}
Point segment_intersection(Point p1,Point p2,Point p3,Point p4) //默认有交点
{
if(relation_point(p1,p2,p3)==0) return p3;
else if(relation_point(p1,p2,p4)==0) return p4;
else if(relation_point(p3,p4,p1)==0) return p1;
else if(relation_point(p3,p4,p2)==0) return p2;
long double t=Cross(p1-p3,p3-p4)/Cross(p1-p2,p3-p4);
long double s=Cross(p1-p3,p1-p2)/Cross(p1-p2,p3-p4);
Point ans;
ans.x=p1.x+t*(p2.x-p1.x); //x=p3.x+s*(p4.x-p3.x);
ans.y=p1.y+t*(p2.y-p1.y); //y=p3.y+s*(p4.y-p4.y);
return ans;
}
long double Distance_segment_to_segment(Point p1,Point p2,Point p3, Point p4)
{
if(Segment_proper_intersection(p1,p2,p3,p4)) return 0.00;
long double ans=1e9;
ans=min(ans,Distance_point_to_segment(p3,p1,p2));
ans=min(ans,Distance_point_to_segment(p4,p1,p2));
ans=min(ans,Distance_point_to_segment(p1,p3,p4));
ans=min(ans,Distance_point_to_segment(p2,p3,p4));
return ans;
}
////多边形
//求多边形面积
int polyg_on_area(vector<Point> &cnt,int n) //n边形
{
int area=0;
for(int i=1;i<=n-2;i++)
{
area+=(int)Cross(cnt[i]-cnt[0],cnt[i+1]-cnt[0]);
}
return area;
}
int is_point_in_polygon(Point p,vector<Point> poly) //判断点是否在多边形内部,是返回1,不是返回0,在多边形上返回-1
{
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;
}
int is_convex(int n,vector<Point> p) //判断是否为凸多边形,顶点按顺时针或者逆时针给出,允许邻边共线
{
int s[3]={1,1,1};
for(int i=0;i<n&&(s[1]|s[2]);i++)
{
s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;
}
return s[1]|s[2];
}
int is_convex_v2(int n,vector<Point> p) //不允许邻边共线
{
int s[3]={1,1,1};
for(int i=0;i<n&&(s[1]|s[2])&&s[0];i++)
{
s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;
}
return s[0]&&s[1]|s[2];
}
Point barycenter(int n,vector<Point> p) //逆时针给点
{
Point ans;
ans.x=0;
ans.y=0;
long double ss=0;
for(int i=1;i<n-1;i++)
{
if(fabs(xmult(p[i],p[i+1],p[0]))>eps) //判断三点不共线
{
long double s=xmult(p[i],p[i+1],p[0]); //即使是非凸四边形,面积最后也会消掉,所以不用加绝对值
ans.x+=(p[0].x+p[i].x+p[i+1].x)*s;
ans.y+=(p[0].y+p[i].y+p[i+1].y)*s;
ss+=s;
}
}
if(fabs(ss)>eps)
{
ans.x/=ss;
ans.x/=3;
ans.y/=ss;
ans.y/=3;
}
return ans;
}
int segment_isin_polygon(Point l1,Point l2,int n,vector<Point> p)//判断线段是否在多边形内(顶点在边上也算在多边形内)
{
if(!is_point_in_polygon(l1,p)||!is_point_in_polygon(l2,p)) return 0;
vector<Point> t;
for(int i=0;i<n;i++)
{
if(segment_proper_intersection(l1,l2,p[i],p[(i+1)%n])) return 0;
else if(OnSegment(l1,p[i],p[(i+1)%n])) t.push_back(l1);
else if(OnSegment(l2,p[i],p[(i+1)%n])) t.push_back(l2);
else if(OnSegment(p[i],l1,l2)) t.push_back(p[i]);
}
sort(t.begin(),t.end()); //或者暴力枚举每两个点
for(int i=0;i<t.size()-1;i++)
{
Point tt;
tt.x=(t[i].x+t[i+1].x)/2;
tt.y=(t[i].y+t[i+1].y)/2;
if(!is_point_in_polygon(tt,p)) return 0;
}
return 1;
}
struct Circle
{
Point c;
long double r;
Circle(Point c=Point(),long double r=0):c(c),r(r){} //Circle c
//若要访问圆心 c.c.x c.c.y
inline Point point(long double a) //通过圆心角求坐标
{
return Point(c.x+cos(a)*r,c.y+sin(a)*r);
}
};
int get_line_circle_intersection(Line L,Circle C,long double &t1,long double &t2,vector<Point>& sol)
{
long double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
long double e = a*a + c*c, f = 2*(a*b + c*d), g = b*b + d*d - C.r*C.r;
long double delta1 = f*f - 4*e*g;// 判别式
if(sgn(delta1) < 0)// 相离
return 0;
if(sgn(delta1) == 0){// 相切
t1 = -f /(2*e);
t2 = -f /(2*e);
sol.push_back(L.get_point_in_line(t1));// sol存放交点本身
return 1;
}
// 相交
t1 = (-f - sqrt(delta1))/(2*e);
sol.push_back(L.get_point_in_line(t1));
t2 = (-f + sqrt(delta1))/(2*e);
sol.push_back(L.get_point_in_line(t2));
return 2;
}
int get_circle_circle_intersection(Circle c1,Circle c2,vector<Point> &sol)
{
long double d = Length(c1.c - c2.c);
if(sgn(d) == 0)
{
if(sgn(c1.r - c2.r) == 0)return -1;// 两圆重合
return 0;
}
if(sgn(c1.r + c2.r - d) < 0)return 0;// 相离
if(sgn(fabs(c1.r - c2.r) - d) > 0)return 0;// 在另一个圆的内部
long double a = atan2((c2.c - c1.c).y,(c2.c-c1.c).x);// 向量c1c2的极角
//cout<<a<<"dd"<<endl;
long double da = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d));
// c1c2到c1p1的角
Point p1 = c1.point(a - da), p2 = c1.point(a + da);
sol.push_back(p1);
if(p1 == p2)return 1;
sol.push_back(p2);
return 2;
}
// 过点p到圆c的切线,v[i]是第i条切线, 返回切线的条数
int get_tangents(Point p, Circle C, vector<Vector> &k)
{
Vector u = C.c - p;
long double dist = Length(u);
if(dist < C.r)return 0;// 点在内部,没有切线
else if(sgn(dist - C.r) == 0)
{// p在圆上,只有一条切线
k.push_back(Rotate(u,pi/2));
//v[0] = Rotate(u, pi / 2);// 切线就是垂直嘛
return 1;
}
else
{// 否则是两条切线
long double ang = asin(C.r / dist);
k.push_back(Rotate(u,-ang));
k.push_back(Rotate(u,+ang));
// v[0] = Rotate(u, - ang);
// v[1] = Rotate(u, +ang);
return 2;
}
}
int get_tangents_point(Point p,Circle c,vector<Point> &k)
{
vector<Vector> ans;
int cnt=get_tangents(p,c,ans);
if(cnt==0) return 0; //点在圆内
if(cnt==1)
{
Line l(ans[0],p);
long double t1,t2;
int u=get_line_circle_intersection(l,c,t1,t2,k);
// for(int i=0;i<=1;i++)
// {
// std::cout << std::fixed << std::setprecision(8) <<kk[0].x<<' '<<kk[0].y<<endl;
// }
return 1;
}
else
{
Line l1(ans[0],p);
Line l2(ans[1],p);
vector<Point> kk;
long double t1,t2;
int u=get_line_circle_intersection(l1,c,t1,t2,k);
u=get_line_circle_intersection(l2,c,t1,t2,k);
sort(k.begin(),k.end());
// for(int i=0;i<=1;i++)
// {
// std::cout << std::fixed << std::setprecision(8) <<kk[i].x<<' '<<kk[i].y<<endl;
// }
return 2;
}
}
inline Circle getcircle(Point A,Point B,Point C) //求外接圆
{// 【三点确定一圆】向量垂直平分线法
Point P1=(A+B)*0.5,P2=(A+C)*0.5;
Point O=Get_line_intersection(P1,Normal(B-A),P2,Normal(C-A));
return Circle(O,Length(A-O));
}
Circle NeiJieYuan(Point p1,Point p2,Point p3) //求内接圆
{
long double a=Length(p2-p3);
long double b=Length(p3-p1);
long double c=Length(p1-p2);
Point p=(p1*a+p2*b+p3*c)/(a+b+c);
return Circle(p,Distance_point_to_line(p,p1,p2));
}
Circle WaiJieYuan(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));
}
// 返回切线的条数,-1表示无穷条切线
// /a[i]和b[i] 分别是第i条切线在圆A和圆B上的切点
int get_circletangents(Circle A, Circle B, vector<Point> &a, vector<Point>&b)
{
int cnt = 0;
if(A.r < B.r)swap(A, B), swap(a, b); //注意这里交换了,如果A.r<B.r 那么b里面存a的切点
int d2 = (A.c.x - B.c.x) * (A.c.x - B.c.x) + (A.c.y - B.c.y) * (A.c.y - B.c.y);
int rdiff = A.r - B.r;
int rsum = A.r + B.r;
if(d2 < rdiff * rdiff)return 0;// 内含
double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);
if(d2 == 0 & A.r == B.r)return -1;// 无限多条切线
if(d2 == rdiff * rdiff)
{// 内切,1条切线
a.push_back( A.point(base));
b.push_back( B.point(base)); cnt ++ ;
return 1;
}
// 有外共切线
double ang = acos((A.r - B.r) / sqrt(d2));
a.push_back( A.point(base + ang));b.push_back( B.point(base + ang));cnt ++ ;
a.push_back(A.point(base - ang));b.push_back(B.point(base - ang));cnt ++ ;
if(d2 == rsum * rsum)
{ // 一条内公切线
a.push_back(A.point(base));b.push_back(B.point(pi + base)); cnt ++ ;
}
else if(d2 > rsum * rsum)
{ // 两条内公切线
double ang = acos((A.r + B.r) / sqrt(d2));
a.push_back(A.point(base + ang)); b.push_back(B.point(pi + base + ang)); cnt ++ ;
a.push_back(A.point(base - ang)); b.push_back(B.point(pi + base - ang)); cnt ++ ;
}
return cnt;
}
//通过计算两个圆相交所构成的两个扇形面积和减去其构成的筝形的面积
long double AreaOfOverlap(Point c1, long double r1, Point c2, long double r2) //求两圆相交面积
{
long double d = Length(c1 - c2);
//cout<<c2.x<<endl;
if(r1 + r2 < d + eps)
return 0.0;
if(d < fabs(r1 - r2) + eps)
{
long double r = min(r1, r2);
return pi*r*r;
}
long double x = (d*d + r1*r1 - r2*r2)/(2.0*d);
long double p = (r1 + r2 + d)/2.0;
long double t1 = acos(x/r1);
long double t2 = acos((d - x)/r2);
long double s1 = r1*r1*t1;
long double s2 = r2*r2*t2;
long double s3 = 2*sqrt(p*(p - r1)*(p - r2)*(p - d));
return s1 + s2 - s3;
}
int grid_onedge(int n,vector<Point> p) //返回多边形边上的网格点个数 s=in+(edge/2)-1 //面积s可以通过三角剖分叉积算
{
int ret=0;
for (int i=0;i<n;i++ )
ret+=__gcd(abs((int)p[i].x-(int)p[(i+1)%n].x),abs((int)p[i].y-(int)p[(i+1)%n].y));
return ret;
}
bool argcmp(const Point &a,const Point &b) //下半平面<原点<x正半轴<上半平面<x负半轴
{
auto quad=[](const Point &a)
{
if(a.y<-eps) return 1; //在下半平面
if(a.y>eps) return 4; //在上半平面
if(a.x<-eps) return 5;//在负x轴
if(a.x>eps) return 3;//在正x轴
return 2;//在原点
};
int qa=quad(a),qb=quad(b);
if(qa!=qb) return qa<qb;
int t=(int)Cross(a,b);
if(abs(t)<=eps) return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y-eps; //如果t等0,说明他们的极角一样,这时候按照长度比
return t>eps;
}
// 计算凸包,输入点数组p,个数为p输出点数组ch,函数返回凸包顶点个数。
// 输入不能有重复的点,函数执行完后的输入点的顺序将被破坏(因为要排序,可以加一个数组存原来的id)
// 如果不希望在凸包边上有输入点,把两个< 改成<=即可
int ConvexHull(vector<Point> &p, int n, vector<Point> &ch)
{
sort(p.begin(), p.begin() + n);
int m = 0;
for(int i = 0; i < n; ++ i)
{// 下凸包
// 如果叉积<= 0说明新边斜率小说明已经不是凸包边了,赶紧踢走
while(m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <=0)
{
m--;
ch.pop_back();
}
ch.push_back(p[i]);
// flag[i]=1;
m++;
}
int k = m;
for(int i = n - 2; i >= 0; -- i)
{// 上凸包
while(m > k && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <=0)
{
m--;
ch.pop_back();
}
ch.push_back(p[i]);
m++;
}
if(n > 1) m -- ;
return m;
}
long double Convex_hull_diameter(vector<Point> p,int num) //返回直径平方,p必须没有三点共线的凸包
{
if(num==2)
{
return (int)Dis_point_to_point2(p[0],p[1]);
}
if(num==3)
{
return max({(int)Dis_point_to_point2(p[0],p[1]),(int)Dis_point_to_point2(p[0],p[2]),(int)Dis_point_to_point2(p[1],p[2])});
}
p.push_back(p[0]);
int pos=2;
long double ans=-1e8;
for(int i=0;i<p.size()-1;i++)
{
auto p1=p[i];
auto p2=p[i+1];
auto p3=p[pos];
auto t=Area2(p1,p2,p3);
long double maxx=t;
int j=pos;
while(j<p.size()-1&&Area2(p1,p2,p[j])>=maxx)
{
//j++;
maxx=Area2(p1,p2,p[j]);
ans=max({ans,Dis_point_to_point2(p1,p[j]),Dis_point_to_point2(p2,p[j])});
j++;
}
pos=j-1;
}
return ans;
}
int is_in_convexhull(vector<Point> &p,Point t,int n) //n>=3,逆时针,要传数组指针
{
if(t==p[0])
{
return 0;
}
if(OnSegment(t,p[0],p[1]))
{
return 0;
}
if(OnSegment(t,p[0],p[n-1]))
{
return 0;
}
if(ToLeftTest(p[0],p[n-1],t))
{
return 1;
}
if(ToLeftTest(p[1],p[0],t))
{
return 1;
}
int l=2,r=n-1;
while(l<r)
{
int mid=l+r>>1;
if(ToLeftTest(p[0],p[mid],t)) l=mid+1;
else r=mid;
}
Point t1=p[l-1];
Point t2=p[l];
if(OnSegment(t,t1,t2))
{
return 0;
}
//cout<<t1.x<<"pa"<<t1.y<<endl;
if(ToLeftTest(t1,t2,t))
{
return -1;
}
else return 1;
}
void solve(int u)
{
// long double number = 3.14159265358979323846;
// // 使用流操纵器保留6位小数并输出
// std::cout << std::fixed << std::setprecision(6) << number << std::endl;
// cout<<"aaa"<<endl;
int n;
cin>>n;
vector<Point> a;
for(int i=1;i<=n;i++)
{
Point t;
cin>>t.x>>t.y;
t.z=i;
a.push_back(t);
}
// if(T==7&&u==5)
// {
// cout<<a[0].x<<" "<<a[0].y<<" "<<a[1].x<<" "<<a[1].y<<" "<<a[2].x<<" "<<a[2].y<<" "<<a[3].x<<" "<<a[3].y<<" "<<a[4].x<<" "<<a[4].y<<" "<<a[5].x<<" "<<a[5].y<<endl;
// return ;
// }
vector<Point> convh;
int m=ConvexHull(a,n,convh);
vector<Point> tt;
set<int> se;
for(int i=0;i<convh.size();i++)
{
se.insert(convh[i].z);
}
for(int i=0;i<a.size();i++)
{
if(se.count(a[i].z)==0) tt.push_back(a[i]);
}
vector<Point> convh1;
int m1=ConvexHull(tt,tt.size(),convh1);
if(m1==0)
{
cout<<-1<<endl;
return ;
}
int ans=polyg_on_area(convh,m);
int res=7e18;
if(convh1.size()>1)
convh1.pop_back();
convh.pop_back();
//sort(convh1.begin(),convh1.end());
// sort(convh.begin(),convh.end());
int idx=0;
// for(int i=0;i<convh.size();i++)
// {
// cout<<convh[i].x<<" "<<convh[i].y<<endl;
// }
// cout<<"aa"<<endl;
// for(int i=0;i<convh1.size();i++)
// {
// cout<<convh1[i].x<<' '<<convh1[i].y<<endl;
// }
// cout<<"aa"<<endl;
// cout<<m<<"aaaaa"<<m1<<endl;
if(m1==1)
{
auto t=convh1[0];
for(int i=0;i<convh.size();i++)
{
res=min(res,abs((int)Cross(convh[i]-t,convh[(i+1)%m]-t)));
}
cout<<ans-res<<endl;
return ;
}
multiset<int> see;
int num=0;
for(int i=0;i<convh.size();i++)
{
long double cnt=7e18;
Point kk;
auto t1=convh[i];
auto t2=convh[(i+1)%m];
int flag=0;
// cnt=Distance_point_to_line(convh1[idx],t1,t2);
// idx++;
//idx%=m1;
//int num=0;
while(Distance_point_to_line(convh1[idx],t1,t2)<cnt)
{
//cout<<idx<<"aa"<<endl;
num++;
cnt=min(cnt,Distance_point_to_line(convh1[idx],t1,t2));
// see.insert(idx);
kk=convh1[idx];
idx++;
// cout<<"aa"<<endl;
idx%=m1;
flag=1;
}
res=min(res,abs((int)Cross(t1-kk,t2-kk)));
if(flag)
{
idx=(idx-1+m1)%m1;
}
// cout<<idx<<"aa"<<endl;
}
// for(int i=0;i<convh1.size();i++)
// {
// auto t=convh1[i];
// for(int j=0;j<convh.size();j++)
// {
// res=min(res,abs((int)Cross(convh[j]-t,convh[(j+1)%m]-t)));
// }
// }
cout<<ans-res<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>T;
//cout<<acos(-1.0)<<endl;
for(int i=1;i<=T;i++)
{
solve(i);
}
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3856kb
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: 3804kb
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: 0
Accepted
time: 55ms
memory: 3888kb
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 4...
result:
ok 1000 lines
Test #4:
score: 0
Accepted
time: 80ms
memory: 3948kb
input:
10000 9 484630042 51929469 -40468396 -517784096 98214104 -103353239 629244333 -475172587 106398764 153884485 49211709 -44865749 1 10 166321833 -247717657 406208245 668933360 13 548702216 -631976459 37150086 -292461024 707804811 -486185860 239775286 -903166050 10096571 -541890068 686103484 558731937 ...
output:
950319193795831919 1661025342421008544 1285164852091455548 1159924751776806668 1206071151805176722 794021230296144371 699991678992587791 1133990718508584290 1486311831172661605 984875884297072200 1327767982175057345 758247019006396699 1355381234262206155 1139262078529131471 1613462877860621700 12392...
result:
ok 10000 lines
Test #5:
score: 0
Accepted
time: 128ms
memory: 5396kb
input:
100 439 471536154 -312612104 155692036 -937312180 -461624056 -357636609 236656684 -911414873 -288656914 -74788431 -465779694 -381475149 -334197401 -903065737 491513067 -447615916 337664889 -852236281 -281689379 -53519178 -159101704 -920779200 -326159514 -95396204 21868593 -994282736 488425383 -41046...
output:
1973162724053130487 2054612790507830954 1726805687754843724 1699420177872986528 2129388571309147631 2198295137903288810 1697185883164440272 1219697450095721478 2027023581922285255 1674691247127206655 1673105966817209954 2179188692918747442 2146544318743443141 2230356305133660648 1676850321902993764 ...
result:
ok 100 lines
Test #6:
score: 0
Accepted
time: 101ms
memory: 5168kb
input:
100 1362 -467257672 -466669 -467054869 -478108 -466973270 -481776 -466556983 -499770 -466329414 -508693 -466248017 -511805 -466158865 -513786 -466101273 -515035 -465927700 -518748 -465717624 -522106 -465303448 -528127 -465124548 -530726 -464649746 -536693 -464554872 -537799 -464478196 -538680 -46416...
output:
1666097696993497 1791366071767866 1806187278469532 1683419854733713 1685891971828916 1730190225081651 1787048201197565 1850308098208660 1710694884375502 1826363113637639 1816375352374659 2047431269497691 1549806516003854 1829438662895747 1678707854135065 1687423392883819 2121960009997761 16687219538...
result:
ok 100 lines
Test #7:
score: 0
Accepted
time: 64ms
memory: 13532kb
input:
2 62666 -486101704 -505730259 -486101698 -506082699 -486101689 -506111362 -486101682 -506126031 -486101528 -506293759 -486101259 -506556385 -486101196 -506613483 -486101154 -506648604 -486100935 -506831392 -486100631 -507083675 -486100470 -507199151 -486100233 -507368923 -486100193 -507397039 -48609...
output:
2178736946152219010 1825181940245096152
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 153ms
memory: 22012kb
input:
2 100000 301945097 76373292 467957663 -286424714 8245445 -597212507 -474204621 -708828667 184159460 105942538 443435905 -429212625 490658771 -382198656 82512047 -612522436 -228221388 -965890088 394789011 -145801151 -106120174 -528202395 428939626 -194437311 497429477 -527407728 365739746 -114818962 ...
output:
2502889432701099511 2267250485735988121
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 152ms
memory: 20076kb
input:
2 100000 221128057 -975244780 -618765360 -785575858 422567455 -906331476 -988680318 -150037424 -929870145 367887908 -757813541 -652471177 291995621 -956419655 -785381507 619012026 468864522 -883270094 -588416522 808557973 859345881 511394814 988105866 153775152 216931298 -976186873 467050734 8842305...
output:
6283183114882825575 6283183188903854361
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
7 5 -1000000000 -1000000000 1000000000 -1000000000 1000000000 1000000000 1 0 -1 0 5 1000000000 1000000000 -1000000000 -1000000000 -2 0 -1 0 1 -1 6 1000000000 1000000000 -1000000000 -1000000000 -3 0 -1 0 0 -1 1 -1 4 -1000000000 -1000000000 1000000000 -1000000000 1000000000 1000000000 -1000000000 1000...
output:
4000000000000000000 7000000000 9000000001 -1 6000000002000000000 7999999998000000000 -1
result:
ok 7 lines
Extra Test:
score: 0
Extra Test Passed