QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#525432#7521. Find the Gapmhw#WA 1ms3860kbC++235.2kb2024-08-20 16:33:322024-08-20 16:33:33

Judging History

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

  • [2024-08-20 16:33:33]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3860kb
  • [2024-08-20 16:33:32]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-8;
int sgn(double x) {
	if (fabs(x) < eps) return 0;
	if (x < 0) return -1;
	else return 1;
}
struct Point3 {
	double x, y, z;
	Point3(double _x = 0, double _y = 0, double _z = 0) 
	{
		x = _x;
		y = _y;
		z = _z;
	}
	void input() { cin >> x >> y >> z; }
	void output() { cout << fixed << setprecision(8) << x << " " << y << " " << z << '\n'; }
	bool operator==(const Point3 &b) const { return sgn(x - b.x) == 0 && sgn(y - b.y) == 0 && sgn(z - b.z) == 0; }
	bool operator<(const Point3 &b) const { return sgn(x - b.x) == 0 ? (sgn(y - b.y) == 0 ? sgn(z - b.z) < 0 : y < b.y) : x < b.x; }

	double len() { return sqrt(x * x + y * y + z * z); }
	double len2() { return x * x + y * y + z * z; }
	double distance(const Point3 &b) const { return sqrt((x - b.x) * (x - b.x) + (y - b.y) * (y - b.y) + (z - b.z) * (z - b.z)); }

	Point3 operator-(const Point3 &b) const { return Point3(x - b.x, y - b.y, z - b.z); }
	Point3 operator+(const Point3 &b) const { return Point3(x + b.x, y + b.y, z + b.z); }
	Point3 operator*(const double &k) const { return Point3(x * k, y * k, z * k); }
	Point3 operator/(const double &k) const { return Point3(x / k, y / k, z / k); }

	// 点乘
	double operator*(const Point3 &b) const { return x * b.x + y * b.y + z * b.z; }
	// 叉乘
	Point3 operator^(const Point3 &b) const { return Point3(y * b.z - z * b.y, z * b.x - x * b.z, x * b.y - y * b.x); }

	double rad(Point3 a, Point3 b)
	{
		Point3 p = (*this);
		return acos(((a - p) * (b - p)) / (a.distance(p) * b.distance(p)));
	}
	// 变换长度
	Point3 trunc(double r)
	{
		double l = len();
		if (!sgn(l)) return *this;
		r /= l;
		return Point3(x * r, y * r, z * r);
	}
};
struct Line3
{
	Point3 s, e;
	Line3() {}
	Line3(Point3 _s, Point3 _e)
	{
		s = _s;
		e = _e;
	}
	bool operator==(const Line3 v) { return (s == v.s) && (e == v.e); }
	void input()
	{
		s.input();
		e.input();
	}
	double length() { return s.distance(e); }
	// 点到直线距离
	double dispointtoline(Point3 p) { return ((e - s) ^ (p - s)).len() / s.distance(e); }
	// 点到线段距离
	double dispointtoseg(Point3 p)
	{
		if (sgn((p - s) * (e - s)) < 0 || sgn((p - e) * (s - e)) < 0)
			return min(p.distance(s), e.distance(p));
		return dispointtoline(p);
	}
	// 返回点p在直线上的投影
	Point3 lineprog(Point3 p)
	{
		return s + (((e - s) * ((e - s) * (p - s))) / ((e - s).len2()));
	}
	// p绕此向量逆时针arg角度
	Point3 rotate(Point3 p, double ang)
	{
		if (sgn(((s - p) ^ (e - p)).len()) == 0) return p;
		Point3 f1 = (e - s) ^ (p - s);
		Point3 f2 = (e - s) ^ (f1);
		double len = ((s - p) ^ (e - p)).len() / s.distance(e);
		f1 = f1.trunc(len);
		f2 = f2.trunc(len);
		Point3 h = p + f2;
		Point3 pp = h + f1;
		return h + ((p - h) * cos(ang)) + ((pp - h) * sin(ang));
	}
	// 点在直线上
	bool pointonseg(Point3 p)
	{
		return sgn(((s - p) ^ (e - p)).len()) == 0 && sgn((s - p) * (e - p)) == 0;
	}
};
struct Plane
{
	Point3 a, b, c, o; // 平面上的三个点,以及法向量
	Plane() {}
	Plane(Point3 _a, Point3 _b, Point3 _c)
	{
		a = _a;
		b = _b;
		c = _c;
		o = pvec();
	}
	Point3 pvec() { return (b - a) ^ (c - a); }
	// ax + by + cz + d = 0
	Plane(double _a, double _b, double _c, double _d)
	{
		o = Point3(_a, _b, _c);
		if (sgn(_a) != 0) a = Point3((-_d - _c - _b) / _a, 1, 1);
		else if (sgn(_b) != 0) a = Point3(1, (-_d - _c - _a) / _b, 1);
		else if (sgn(_c) != 0) a = Point3(1, 1, (-_d - _a - _b) / _c);
	}
	// 点在平面上的判断
	int pointonplane(Point3 p) { return sgn((p - a) * o); }
	// 两平面夹角
	double angleplane(Plane f) { return acos(o * f.o) / (o.len() * f.o.len()); }
	// 平面和直线的交点,返回值是交点个数
	int crossline(Line3 u, Point3 &p)
	{
		double x = o * (u.e - a);
		double y = o * (u.s - a);
		double d = x - y;
		if (sgn(d) == 0) return 0;
		p = ((u.s * x) - (u.e * y)) / d;
		return 1;
	}
	// 点到平面最近点(也就是投影)
	Point3 pointtoplane(Point3 p)
	{
		Line3 u = Line3(p, p + o);
		crossline(u, p);
		return p;
	}
	// 平面和平面的交线
	int crossplane(Plane f, Line3 &u)
	{
		Point3 oo = o ^ f.o;
		Point3 v = o ^ oo;
		double d = fabs(f.o * v);
		if (sgn(d) == 0) return 0;
		Point3 q = a + (v * (f.o * (f.a - a)) / d);
		u = Line3(q, q + oo);
		return 1;
	}
};
Point3 a[60];
int main()
{
	int n;cin>>n;
	double ans=1e18;
	for(int i=1;i<=n;i++) a[i].input();
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			for(int k=j+1;k<=n;k++)
			{
				Line3 l={a[i],a[j]};
				if(sgn(l.dispointtoline(a[k]))==0) continue;

				Plane p=Plane(a[i],a[j],a[k]);
				double minn=1e18;
				int f;
				for(int o=1;o<=n;o++)
				{
					if(o==i||o==j||o==k) continue;
					int temp=p.pointonplane(a[o]);

					if(o==1) f=temp;
					else if(temp!=0&&f!=temp)
					{
						f=0;
						break;
					}
					
					if(temp==0) continue;
					double dis=a[o].distance(p.pointtoplane(a[o]));
					// cout<<temp<<" "<<i<<" "<<j<<" "<<k<<" "<<o<<" "<<dis<<endl;
					minn=min(minn,dis);
				}
				
				if(f!=0) ans=min(ans,minn); 
			}
		}
	}
	cout<<fixed<<setprecision(12)<<ans<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3852kb

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.000000000000

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

5
1 1 1
1 2 1
1 1 2
1 2 2
2 1 1

output:

0.707106781187

result:

ok found '0.707106781', expected '0.707106781', error '0.000000000'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3856kb

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:

1000000000000000000.000000000000

result:

wrong answer 1st numbers differ - expected: '0.0000000', found: '1000000000000000000.0000000', error = '1000000000000000000.0000000'