QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#617850#9227. Henry the Plumberucup-team5062#WA 1ms3764kbC++173.6kb2024-10-06 17:22:402024-10-06 17:22:40

Judging History

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

  • [2024-10-06 17:22:40]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3764kb
  • [2024-10-06 17:22:40]
  • 提交

answer

#include <cmath>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const long double EPS = 1.0e-8;

class point {
public:
	long double x, y;
	point() : x(0), y(0) {}
	point(long double x_, long double y_) : x(x_), y(y_) {}
	point& operator+=(const point& p) { x += p.x; y += p.y; return *this; }
	point& operator-=(const point& p) { x -= p.x; y -= p.y; return *this; }
	point& operator*=(long double v) { x *= v; y *= v; return *this; }
	point& operator/=(long double v) { x /= v; y /= v; return *this; }
	point operator+(const point& p) const { return point(*this) += p; }
	point operator-(const point& p) const { return point(*this) -= p; }
	point operator*(long double v) const { return point(*this) *= v; }
	point operator/(long double v) const { return point(*this) /= v; }
	long double abs() const { return sqrt(x * x + y * y); }
	long double dot(const point& p) const { return x * p.x + y * p.y; }
	long double cross(const point& p) const { return x * p.y - y * p.x; }
};

class point3d {
public:
	double x, y, z;
	point3d() : x(0), y(0), z(0) {}
	point3d(double x_, double y_, double z_) : x(x_), y(y_), z(z_) {}
	point3d& operator+=(const point3d& p) { x += p.x; y += p.y; z += p.z; return *this; }
	point3d& operator-=(const point3d& p) { x -= p.x; y -= p.y; z -= p.z; return *this; }
	point3d& operator*=(long double v) { x *= v; y *= v; z *= v; return *this; }
	point3d& operator/=(long double v) { x /= v; y /= v; z /= v; return *this; }
	point3d operator+(const point3d& p) const { return point3d(*this) += p; }
	point3d operator-(const point3d& p) const { return point3d(*this) -= p; }
	point3d operator*(long double v) const { return point3d(*this) *= v; }
	point3d operator/(long double v) const { return point3d(*this) /= v; }
	long double abs() const { return sqrt(x * x + y * y + z * z); }
	string to_string() const {
		return "(" + std::to_string(x) + ", " + std::to_string(y) + ", " + std::to_string(z) + ")";
	}
};

point cross_point(const point& s0, const point& s1, const point& t0, const point& t1) {
	long double z = (t0 - s0).cross(t1 - t0) / (s1 - s0).cross(t1 - t0);
	return s0 + (s1 - s0) * z;
}

bool check(const point& p1, const point& p2, const point& p3, const point& p4, long double z1, long double z3) {
	// check parallel case
	if (p2.cross(p4) == 0) {
		return (p3 - p1).dot(p2) == 0;
	}

	// check for non-parallel case
	auto sqr = [&](long double x) -> long double {
		return x * x;
	};
	point3d q1(p1.x, p1.y, z1);
	point3d q3(p3.x, p3.y, z3);
	point z = cross_point(p1, p1 + p2, p3, p3 + p4);
	point3d mp = (q1 + q3) / 2;
	long double r = (q3 - q1).abs() / 2;
	long double d = (z - point(mp.x, mp.y)).abs();
	if (d > r + EPS) {
		return false;
	}
	long double delta = sqrt(r * r - d * d);
	point3d s1(z.x, z.y, mp.z + delta);
	point3d s2(z.x, z.y, mp.z - delta);
	return ((s1 - q1).abs() > EPS && (s1 - q3).abs() > EPS) || ((s2 - q1).abs() > EPS && (s2 - q3).abs() > EPS);
}

int solve(const point& p1, const point& p2, const point& p3, const point& p4, long double z1, long double z3) {
	// case for answer = 2
	if ((p3 - p1).dot(p2) == 0 && (p1 - p3).dot(p4) == 0) {
		return 2;
	}

	// case for answer = 3
	if (check(p1, p2, p3, p4, z1, z3)) {
		return 3;
	}

	return 4;
}

int main() {
	int T;
	cin >> T;
	for (int id = 1; id <= T; id++) {
		point p1, p2, p3, p4; long double z1, z3;
		cin >> p1.x >> p1.y >> z1 >> p2.x >> p2.y;
		cin >> p3.x >> p3.y >> z3 >> p4.x >> p4.y;
		int res = solve(p1, p2, p3, p4, z1, z3);
		cout << res << endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
-1 -1 3
1 1
2 2 3
2 2
5 5 1
3 0
7 6 -2
1 -2

output:

4
3

result:

ok 2 number(s): "4 3"

Test #2:

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

input:

100
-13 -5 -7
-19 19
-19 -13 0
-7 15
-20 20 19
-17 18
20 -20 -1
18 -19
-18 15 -14
-19 18
19 -20 6
20 -19
-12 9 1
7 -16
-13 -14 -8
8 -13
-19 16 9
20 -19
19 -18 -11
19 -18
19 20 -8
12 20
-11 -9 18
-19 -18
8 11 -13
12 -18
18 13 8
4 -18
-16 20 17
-19 18
20 -18 -3
20 -19
-17 -20 -5
-18 -19
19 16 15
19 20...

output:

4
4
4
4
4
3
4
4
4
4
3
4
4
4
4
3
4
4
4
4
4
4
3
4
4
3
4
4
4
3
4
4
4
4
3
4
4
4
4
4
4
4
3
4
4
3
4
4
4
3
3
3
4
4
3
4
4
4
4
4
4
4
3
4
3
4
3
4
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
4
4
4
4
4
4
4
4
4
3
4
4
4
3

result:

wrong answer 6th numbers differ - expected: '4', found: '3'