QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #194039 | #7521. Find the Gap | ucup-team1447# | WA | 104ms | 1700kb | C++23 | 15.0kb | 2023-09-30 18:36:12 | 2023-09-30 18:36:12 |
Judging History
answer
#include <stdio.h>
#include <random>
#include <queue>
std::mt19937_64 rng(0x3d03d);
#include <math.h>
#include <time.h>
#include <assert.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#define int long long
#define ld(x) printf("%lld\n",x)
// #define int unsigned
using std::vector;
using vi=vector<int>;
using pi=std::pair<int,int>;
using vpi=vector<pi>;
#define x first
#define y second
const int mod=998244353;
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a<b?b:a;}
inline int read()
{
int num=0,f=1;char c=getchar();
while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
while(c>47&&c<58)num=num*10+(c^48),c=getchar();
return num*f;
}
typedef int arr[1000005];
#define db double
#define double long double
struct point{db x,y,z;}a[55];
namespace banzi{
using namespace std;
#define MAX_N 110
/*------------------常量区-------------------*/
const double INF = 1e10; // 无穷大
const double EPS = 1e-12; // 计算精度
const double PI = acos(-1.0);// PI
const int PINXING = 0; // 平行
const int XIANGJIAO = 1; // 相交
const int XIANGLI = 3; // 相离
const int GONGXIAN = 2; // 共线
const int CHONGDIE = -1; // 重叠
const int INSIDE = 1; // 点在图形内部
const int OUTSIDE = 0; // 点在图形外部
const int BORDER = 2; // 点在图形边界
/*-----------------类型定义区----------------*/
struct Point { // 二维点或矢量
double x, y;
//double angle, dis;
Point() {}
Point(double x0, double y0): x(x0), y(y0) {}
void read()
{
scanf("%Lf%Lf",&x,&y);
}
};
struct Line { // 二维的直线或线段
Point p1, p2;
Line() {}
Line(Point p10, Point p20): p1(p10), p2(p20) {}
void read()
{
scanf("%Lf%Lf%Lf%Lf",&p1.x,&p1.y,&p2.x,&p2.y);
}
};
struct Rect { // 用长宽表示矩形的方法 w, h分别表示宽度和高度
double w, h;
Rect() {}
Rect(double _w,double _h) : w(_w),h(_h) {}
};
struct Rect_2 { // 表示矩形，左下角坐标是(xl, yl)，右上角坐标是(xh, yh)
double xl, yl, xh, yh;
Rect_2() {}
Rect_2(double _xl,double _yl,double _xh,double _yh) : xl(_xl),yl(_yl),xh(_xh),yh(_yh) {}
};
struct Circle { //圆
Point c;
double r;
Circle() {}
Circle(Point _c,double _r) :c(_c),r(_r) {}
};
typedef vector<Point> Polygon; // 二维多边形
typedef vector<Point> Points; // 二维点集
/*-------------------基本函数区---------------------*/
inline double max(double x,double y)
{
return x > y ? x : y;
}
inline double min(double x, double y)
{
return x > y ? y : x;
}
inline bool ZERO(double x) // x == 0
{
return (fabs(x) < EPS);
}
inline bool ZERO(Point p) // p == 0
{
return (ZERO(p.x) && ZERO(p.y));
}
inline bool EQ(double x, double y) // eqaul, x == y
{
return (fabs(x - y) < EPS);
}
inline bool NEQ(double x, double y) // not equal, x != y
{
return (fabs(x - y) >= EPS);
}
inline bool LT(double x, double y) // less than, x < y
{
return ( NEQ(x, y) && (x < y) );
}
inline bool GT(double x, double y) // greater than, x > y
{
return ( NEQ(x, y) && (x > y) );
}
inline bool LEQ(double x, double y) // less equal, x <= y
{
return ( EQ(x, y) || (x < y) );
}
inline bool GEQ(double x, double y) // greater equal, x >= y
{
return ( EQ(x, y) || (x > y) );
}
// 输出浮点数前，防止输出-0.00调用该函数进行修正！
inline double FIX(double x)
{
return (fabs(x) < EPS) ? 0 : x;
}
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
//-------------------3D 区域----------------------------//
struct Point3D { //三维点或矢量
double x, y, z;
Point3D() {}
Point3D(double x0, double y0, double z0): x(x0), y(y0), z(z0) {}
void read()
{
scanf("%Lf%Lf%Lf",&x,&y,&z);
}
};
struct Line3D { // 三维的直线或线段
Point3D p1, p2;
Line3D() {}
Line3D(Point3D p10, Point3D p20): p1(p10), p2(p20) {}
void read()
{
scanf("%Lf%Lf%Lf%Lf%Lf%Lf",&p1.x,&p1.y,&p1.z,&p2.x,&p2.y,&p2.z);
}
};
struct Area3D{
Point3D p1,p2,p3;
Area3D(){}
Area3D(Point3D p10, Point3D p20,Point3D p30): p1(p10), p2(p20), p3(p30){}
void read()
{
p1.read(); p2.read(); p3.read();
//scanf("%Lf%Lf%Lf%Lf%Lf%Lf%Lf%Lf%Lf",&p1.x,&p1.y,&p1.z,&p2.x,&p2.y,&p2.z,&p3.x,&p3.y,&p3.z);
}
};
inline bool ZERO(Point3D p) // p == 0
{
return (ZERO(p.x) && ZERO(p.y) && ZERO(p.z));
}
//////////////////////////////////////////////////////////////////////////////////////
//三维矢量运算
bool operator==(Point3D p1, Point3D p2)
{
return ( EQ(p1.x, p2.x) && EQ(p1.y, p2.y) && EQ(p1.z, p2.z) );
}
bool operator<(Point3D p1, Point3D p2)
{
if (NEQ(p1.x, p2.x)) {
return (p1.x < p2.x);
} else if (NEQ(p1.y, p2.y)) {
return (p1.y < p2.y);
} else {
return (p1.z < p2.z);
}
}
Point3D operator+(Point3D p1, Point3D p2)
{
return Point3D(p1.x + p2.x, p1.y + p2.y, p1.z + p2.z);
}
Point3D operator-(Point3D p1, Point3D p2)
{
return Point3D(p1.x - p2.x, p1.y - p2.y, p1.z - p2.z);
}
Point3D operator * (const Point3D& A, double p) { return Point3D(A.x*p, A.y*p, A.z*p); }
Point3D operator / (const Point3D& A, double p) { return Point3D(A.x/p, A.y/p, A.z/p); }
Point3D operator*(Point3D p1, Point3D p2) // 计算叉乘 p1 x p2
{
return Point3D(p1.y * p2.z - p1.z * p2.y,
p1.z * p2.x - p1.x * p2.z,
p1.x * p2.y - p1.y * p2.x );
}
double operator&(Point3D p1, Point3D p2) { // 计算点积 p1·p2
return (p1.x * p2.x + p1.y * p2.y + p1.z * p2.z);
}
double Norm(Point3D p) // 计算矢量p的模
{
return sqrt(p.x * p.x + p.y * p.y + p.z * p.z);
}
//取平面法向量
Point3D GetV(Area3D s){
return (s.p1-s.p2)*(s.p2-s.p3);
}
//判三点共线
int PointOnLine(Point3D p1,Point3D p2,Point3D p3){
return ZERO( (p1-p2)*(p2-p3) );
}
//判四点共面
int PointOnArea(Point3D a,Point3D b,Point3D c,Point3D d){
return ZERO( GetV(Area3D(a, b, c))&(d-a) );
}
//求三维空间中两点间的距离
double Dis(Point3D p1, Point3D p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z));
}
// 求三维空间中点到直线的距离
double Dis(Point3D p, Line3D L)
{
if(L.p1==L.p2) return Dis(p, L.p1);
return Norm((p - L.p1) * (L.p2 - L.p1)) / Norm(L.p2 - L.p1);
}
bool OnLine(Point3D p, Line3D L) // 判断三维空间中点p是否在直线L上
{
if(L.p1==L.p2 && p==L.p1) return true;//共点时，返回true
return ZERO( (p - L.p1) * (L.p2 - L.p1) );
}
bool OnLineSeg(Point3D p, Line3D L) // 判断三维空间中点p是否在线段l上
{
return ( ZERO((L.p1 - p) * (L.p2 - p)) &&
EQ( Norm(p - L.p1) + Norm(p - L.p2), Norm(L.p2 - L.p1)) );
}
// 点p到平面Ap-Al的距离。
double Dis(Point3D p, Point3D Ap, Point3D Al) {
return fabs((p-Ap)&Al)/Norm(Al); // 如果不取绝对值，得到的是有向距离
}
// 点p在平面Ap-Al上的投影。
Point3D PointToArea(Point3D p,Point3D Ap, Point3D Al) {
Al=Al/(Norm(Al));//把Al变成法向量。
return p-Al*((p-Ap)&Al);
}
//得到点p到直线L的距离，并返回p到直直线L的最近点rep
double PointToLine(Point3D p,Line3D L,Point3D& rep)
{
if(L.p1==L.p2)
{
rep=L.p1;
return Dis(p,L.p1);
}
Point3D a,b;
a = L.p2-L.p1;
b = p-L.p1;
double dis12 = Dis(L.p1,L.p2);
double dis = ( Norm(a*b) )/dis12;
double k = (a&b)/(Norm(a)*dis12) ;
rep = L.p1+(L.p2-L.p1)*k;
return dis;
}
//求两条直线之间的关系（三维）
//输入：两条不为点的直线
//输出：相交返回XIANGJIAO和交点p,平行返回PINGXING,共线返回GONGXIAN
int LineAndLine(Line3D L1,Line3D L2,Point3D &p)
{
Point3D px,py;
px = L1.p1 - L1.p2;
py = L2.p1 - L2.p2;
if( ZERO(px*py) )//平行或者共线
{
if( ZERO( (L2.p1-L1.p1)*py ) ) //共线
{
return GONGXIAN;
}
return PINXING;
}
//判断是否共面
Point3D tp=(L1.p1-L2.p1)*py;
if( !ZERO(tp&px) ) return XIANGLI;//XIANGLI与平行相同
p = L1.p1;
Point3D tp1=(L2.p1-L1.p1)*(L2.p1-L2.p2);
Point3D tp2=(L1.p2-L1.p1)*(L2.p1-L2.p2);
double _t = Norm(tp1)/Norm(tp2);
//tp1和tp2肯定是共线的，如果反向则_t 为负
if( LT( (tp1&tp2),0 ) ) _t*=-1;
p.x += (L1.p2.x-L1.p1.x)*_t;
p.y += (L1.p2.y-L1.p1.y)*_t;
p.z += (L1.p2.z-L1.p1.z)*_t;
return XIANGJIAO;
}
//空间两直线最近点对。直线不能平行，直线不能为点.
//ans1为直线a1,b1上的最近点
Point3D ans1,ans2;
double SegSegDistance(Point3D a1, Point3D b1, Point3D a2, Point3D b2)
{
Point3D v1 = (a1-b1), v2 = (a2-b2);
Point3D N = v1*v2;
Point3D ab = (a1-a2);
double ans = (N&ab) / Norm(N);
Point3D p1 = a1, p2 = a2;
Point3D d1 = b1-a1, d2 = b2-a2;
double t1, t2;
t1 = ((p2-p1)*d2 )&(d1*d2);
t2 = ((p2-p1)*d1 )&(d1*d2);
double dd = Norm( (d1*d2) );
t1 /= dd*dd;
t2 /= dd*dd;
ans1=a1+(b1-a1)*t1;
ans2=a2+(b2-a2)*t2;
return fabs(ans);
}
//直线与平面交
int LineAndArea(Line3D l1,Point3D Ap,Point3D Al,Point3D &p)
{
//输入直线，和平面的点法式
//第一步，判断直线与平面是否平行。
if( ZERO((l1.p2-l1.p1)&Al) ) return 0;//直线与平面平行。
double _t =( (Ap-l1.p1)&Al ) / ((l1.p1-l1.p2)&Al);
p = l1.p1+(l1.p1-l1.p2)*_t;
return 1;
}
void dfs(int x,double &len)
{
len++;
dfs(x-1,len);
dfs(x-2,len);
}
//空间两直线最近点对
//注意：直线不能平行
double LineAndLine(Line3D l1,Line3D l2,Point3D &p1,Point3D &p2)
{
//先求出法向量
Point3D v1,v2;
v1 = l1.p2-l1.p1;
v2 = l2.p2-l2.p1;
Point3D vt=v1*v2;
//然后先把l2投影到 l1所在的平面上
double len = ((l2.p1-l1.p1)&vt)/Norm(vt);
double normvt = -len/Norm(vt);
vt.x = vt.x*normvt;
vt.y = vt.y*normvt;
vt.z = vt.z*normvt;
Line3D tl2;
tl2.p1 = l2.p1+vt;
tl2.p2 = l2.p2+vt;
int sign=LineAndLine(l1, tl2, p1);
/*
//测试用
if(sign!=XIANGJIAO)
{
int x=0;
printf("%Lf\n",len/x);
dfs(100000000,len);
}
*/
return fabs(len);
}
//已知空间四面体6条边，求体积
double P( double a,double b,double c,double d,double e ){ return a*(b*c-d*e); }
double Get4V(int OA,int OB,int OC,int AB,int CA,int BC)
{
OA*=OA;OB*=OB;OC*=OC;AB*=AB;CA*=CA;BC*=BC;
double ans=0;
ans+=P( OA,OB,OC,(OB+OC-BC)/2.0,(OB+OC-BC)/2.0 );
ans-=P( (OA+OB-AB)/2.0,(OA+OB-AB)/2.0,OC,(OA+OC-CA)/2.0,(OB+OC-BC)/2.0 );
ans+=P( (OA+OC-CA)/2.0,(OA+OB-AB)/2.0,(OB+OC-BC)/2.0,OB,(OA+OC-CA)/2.0);
return sqrt(ans/36);
}
//求两面相交,平行或共面返回PINGXING,否则返回XIANGJIAO和直线rel
int AreaAndArea(Area3D a1,Area3D a2,Line3D &rel)
{
Point3D va1 = GetV(a1),va2 = GetV(a2);
Point3D lv = va1*va2;//相交直线的方向向量
if( ZERO(lv) )//平行
{
return PINXING;
}
//然后得到某一个交点
Point3D p1;
if(LineAndArea(Line3D(a1.p1,a1.p2), a2.p1, va2, p1) == 0)
if(LineAndArea(Line3D(a1.p1,a1.p3), a2.p1, va2, p1) == 0)
LineAndArea(Line3D(a1.p2,a1.p3), a2.p1, va2, p1);
rel.p1 = p1; rel.p2 = p1 + (lv*10);
return XIANGJIAO;
}
//已知3点坐标，求平面ax+by+cz+d=0;
void GetAreaABCD(Point3D p1,Point3D p2,Point3D p3,double &a,double &b,double &c,double &d)
{
a = ( (p2.y-p1.y)*(p3.z-p1.z)-(p2.z-p1.z)*(p3.y-p1.y) );
b = ( (p2.z-p1.z)*(p3.x-p1.x)-(p2.x-p1.x)*(p3.z-p1.z) );
c = ( (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x) );
d = ( 0-(a*p1.x+b*p1.y+c*p1.z) );
}
//////////////////////////////////////////////////////////////////////////////////////
/*---------------------代码区---------------------------*/
}
signed main()
{
int n=read();
for(int i=1;i<=n;i++)a[i].x=read(),a[i].y=read(),a[i].z=read();
double ans=1e18;
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
{
db A=a[i].x-a[j].x;
db B=a[i].y-a[j].y;
db C=a[i].z-a[j].z;
db xs=sqrt(A*A+B*B+C*C);
db mn=1e18,mx=-1e18;
for(int k=1;k<=n;k++)
mn=std::min(mn,A*a[k].x+B*a[k].y+C*a[k].z),
mx=std::max(mx,A*a[k].x+B*a[k].y+C*a[k].z);
ans=std::min(ans,(mx-mn)/xs);
}
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
for(int k=1;k<=n;k++)if(k!=i&&k!=j)
{
banzi::Point3D A1(a[i].x,a[i].y,a[i].z);
banzi::Point3D B1(a[j].x,a[j].y,a[j].z);
banzi::Point3D C1(a[k].x,a[k].y,a[k].z);
banzi::Line3D l(A1,B1);
banzi::Point3D Q;
double zz=banzi::PointToLine(C1,l,Q);
// printf("%d %d %d:%.3lf\n",i,j,k,zz);
auto [A,B,C]=Q;
A-=a[k].x;
B-=a[k].y;
C-=a[k].z;
db xs=sqrt(A*A+B*B+C*C);
db mn=1e18,mx=-1e18;
for(int k=1;k<=n;k++)
mn=std::min(mn,A*a[k].x+B*a[k].y+C*a[k].z),
mx=std::max(mx,A*a[k].x+B*a[k].y+C*a[k].z);
// if((mx-mn)/xs<1)printf("%d %d %d\n",i,j,k);
ans=std::min(ans,(mx-mn)/xs);
}
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
for(int k=1;k<j;k++)
{
banzi::Point3D A1(a[i].x,a[i].y,a[i].z);
banzi::Point3D B1(a[j].x,a[j].y,a[j].z);
banzi::Point3D C1(a[k].x,a[k].y,a[k].z);
banzi::Line3D l(A1,B1);
banzi::Point3D Q;
double zz=banzi::PointToLine(C1,l,Q);
if(zz<1e-10)continue;
banzi::Area3D T(A1,B1,C1);
auto [A,B,C]=banzi::GetV(T);
// printf("%d %d %d:%.3lf\n",i,j,k,zz);
db xs=sqrt(A*A+B*B+C*C);
db mn=1e18,mx=-1e18;
for(int k=1;k<=n;k++)
mn=std::min(mn,A*a[k].x+B*a[k].y+C*a[k].z),
mx=std::max(mx,A*a[k].x+B*a[k].y+C*a[k].z);
ans=std::min(ans,(mx-mn)/xs);
}
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
for(int k=1;k<i;k++)
for(int l=1;l<k;l++)if(l!=j)
{
banzi::Point3D A1(a[i].x,a[i].y,a[i].z);
banzi::Point3D B1(a[j].x,a[j].y,a[j].z);
banzi::Point3D C1(a[k].x,a[k].y,a[k].z);
banzi::Point3D D1(a[l].x,a[l].y,a[l].z);
banzi::Line3D x(A1,B1);
banzi::Line3D y(C1,D1);
banzi::Point3D Q;
if(banzi::LineAndLine(x,y,Q)!=3)continue;
banzi::Point3D A2,B2;
banzi::LineAndLine(x,y,A2,B2);
auto [A,B,C]=A2-B2;
// printf("%d %d %d:%.3lf\n",i,j,k,zz);
db xs=sqrt(A*A+B*B+C*C);
db mn=1e18,mx=-1e18;
for(int k=1;k<=n;k++)
mn=std::min(mn,A*a[k].x+B*a[k].y+C*a[k].z),
mx=std::max(mx,A*a[k].x+B*a[k].y+C*a[k].z);
ans=std::min(ans,(mx-mn)/xs);
}
printf("%.16Lf\n",ans);
fprintf(stderr,"%.12lf\n",1.*clock()/CLOCKS_PER_SEC);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 1656kb
input:
8 1 1 1 1 1 2 1 2 1 1 2 2 2 1 1 2 1 2 2 2 1 2 2 2
output:
1.0000000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 1700kb
input:
5 1 1 1 1 2 1 1 1 2 1 2 2 2 1 1
output:
0.7071067811865475
result:
ok found '0.707106781', expected '0.707106781', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 104ms
memory: 1648kb
input:
50 973 1799 4431 1036 1888 4509 1099 1977 4587 1162 2066 4665 1225 2155 4743 1288 2244 4821 1351 2333 4899 1414 2422 4977 1540 2600 5133 1603 2689 5211 1666 2778 5289 1729 2867 5367 1792 2956 5445 1855 3045 5523 1918 3134 5601 1981 3223 5679 2044 3312 5757 2107 3401 5835 2170 3490 5913 2296 3668 606...
output:
3465.0000000000000000
result:
wrong answer 1st numbers differ - expected: '0.0000000', found: '3465.0000000', error = '3465.0000000'