QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#513785#9168. Square Locatorucup-team1074#WA 0ms3712kbC++2014.0kb2024-08-10 19:41:322024-08-10 19:41:34

Judging History

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

  • [2024-08-10 19:41:34]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3712kb
  • [2024-08-10 19:41:32]
  • 提交

answer

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

// `计算几何模板`

typedef long double db;
const double eps = 1e-7;
const double inf = 1e20;
const double pi = acos (-1.0);
const int maxp = 1001; // 太大的话拷贝会很慢;
//`Compares a double to zero`
int sgn (db x) {
	// if (fabs (x) < eps)return 0;
	// if (x < 0)return -1;
	// else return 1;
	return x < -eps ? -1 : x > eps;
}
// square of a db
inline db sqr (db x) { return x * x; }
/*
 * Point
 * Point()               - Empty constructor
 * Point(db _x,db _y)  - constructor
 * input()             - db input
 * output()            - %.2f output
 * operator ==         - compares x and y
 * operator <          - compares first by x, then by y
 * operator -          - return new Point after subtracting curresponging x and
 * y operator ^          - cross product of 2d points operator *          - dot
 * product len()               - gives length from origin len2()              -
 * gives square of length from origin distance(Point p)   - gives distance from
 * p operator + Point b  - returns new Point after adding curresponging x and y
 * operator * db k - returns new Point after multiplieing x and y by k
 * operator / db k - returns new Point after divideing x and y by k
 * rad(Point a,Point b)- returns the angle of Point a and Point b from this
 * Point trunc(db r)     - return Point that if truncated the distance from
 * center to r rotleft()           - returns 90 degree ccw rotated point
 * rotright()          - returns 90 degree cw rotated point
 * rotate(Point p,db angle) - returns Point after rotateing the Point centering
 * at p by angle radian ccw
 */
struct Point {
	db x{}, y{};
	Point () {}
	Point (db _x, db _y) {
		x = _x;
		y = _y;
	}
	void input () {
		// scanf("%lf%lf", &x, &y);
		cin >> x >> y;
	}
	void output () {
		// printf("%.2f %.2f\n", x, y);
		cout << x << " " << y << "\n";
	}
	bool operator== (Point b) const {
		return sgn (x - b.x) == 0 && sgn (y - b.y) == 0;
	}
	bool operator< (Point b) const {
		return sgn (x - b.x) == 0 ? sgn (y - b.y) < 0 : x < b.x;
	}
	Point operator- (const Point& b) const { return { x - b.x, y - b.y }; }
	Point operator+ (const Point& b) const { return { x + b.x, y + b.y }; }
	Point operator* (const db& k) const { return { x * k, y * k }; }
	Point operator/ (const db& k) const { return { x / k, y / k }; }
	// 叉积
	db operator^ (const Point& b) const { return x * b.y - y * b.x; }
	// 点积
	db operator* (const Point& b) const { return x * b.x + y * b.y; }
	// 返回长度
	double len () {
		// return hypot(x, y); //库函数(慢?精度高)
		return sqrt (x * x + y * y);
	}
	// 返回长度的平方
	db len2 () { return x * x + y * y; }
	// 返回两点的距离
	db distance (Point p) { return hypot (x - p.x, y - p.y); }
	//`计算pa  和  pb 的夹角`
	//`就是求这个点看a,b 所成的夹角`
	//`测试 LightOJ1203`
	double rad (Point a, Point b) {
		Point p = *this;
		return fabs (atan2 (fabs ((a - p) ^ (b - p)), (a - p) * (b - p)));
	}
	//`化为长度为r的向量`
	Point trunc (db r) {
		db l = len ();
		if (!sgn (l))
			return *this;
		r /= l;
		return { x * r, y * r };
	}
	//`逆时针旋转90度`
	Point rotleft () { return { -y, x }; }
	//`顺时针旋转90度`
	Point rotright () { return { y, -x }; }
	//`绕着p点逆时针旋转angle`
	Point rotate (Point p, db angle) {
		Point v = (*this) - p;
		db c = cos (angle), s = sin (angle);
		return { p.x + v.x * c - v.y * s, p.y + v.x * s + v.y * c };
	}
	int quad () {
		// double x = a.x, y = a.y;
		return sgn (y) == 1 || (sgn (y) == 0 && sgn (x) >= 0);
	}
};
//`AB X AC`
db cross (Point A, Point B, Point C) { return (B - A) ^ (C - A); }
//`AB*AC`
db dot (Point A, Point B, Point C) { return (B - A) * (C - A); }

// 极角排序
bool cmp (Point a, Point b) {
	int qa = a.quad (), qb = b.quad ();
	if (qa != qb)
		return qa < qb;
	else
		return sgn (a ^ b) > 0;
}

/*
 * Stores two points
 * Line()                         - Empty constructor
 * Line(Point _s,Point _e)        - Line through _s and _e
 * operator ==                    - checks if two points are same
 * Line(Point p,db angle)     - one end p , another end at angle degree
 * Line(db a,db b,db c) - Line of equation ax + by + c = 0
 * input()                        - inputs s and e
 * adjust()                       - orders in such a way that s < e
 * length()                       - distance of se
 * angle()                        - return 0 <= angle < pi
 * relation(Point p)              - 3 if point is on line
 *                                  1 if point on the left of line
 *                                  2 if point on the right of line
 * pointonseg(db p)           - return true if point on segment
 * parallel(Line v)               - return true if they are parallel
 * segcrossseg(Line v)            - returns 0 if does not intersect
 *                                  returns 1 if non-standard intersection
 *                                  returns 2 if intersects
 * linecrossseg(Line v)           - line and seg
 * linecrossline(Line v)          - 0 if parallel
 *                                  1 if coincides
 *                                  2 if intersects
 * crosspoint(Line v)             - returns intersection point
 * dispointtoline(Point p)        - distance from point p to the line
 * dispointtoseg(Point p)         - distance from p to the segment
 * dissegtoseg(Line v)            - distance of two segment
 * lineprog(Point p)              - returns projected point p on se line
 * symmetrypoint(Point p)         - returns reflection point of p over se
 *
 */
struct Line {
	Point s, e;
	Line () {}
	Line (Point _s, Point _e) {
		s = _s;
		e = _e;
	}
	bool operator== (Line v) { return (s == v.s) && (e == v.e); }
	//`根据一个点和倾斜角angle确定直线,0<=angle<pi`
	Line (Point p, db angle) {
		s = p;
		if (sgn (angle - pi / 2) == 0) {
			e = (s + Point (0, 1));
		}
		else {
			e = (s + Point (1, tan (angle)));
		}
	}
	// ax+by+c=0
	Line (db a, db b, db c) {
		if (sgn (a) == 0) {
			s = Point (0, -c / b);
			e = Point (1, -c / b);
		}
		else if (sgn (b) == 0) {
			s = Point (-c / a, 0);
			e = Point (-c / a, 1);
		}
		else {
			s = Point (0, -c / b);
			e = Point (1, (-c - a) / b);
		}
	}
	void input () {
		s.input ();
		e.input ();
	}
	void adjust () {
		if (e < s)
			swap (s, e);
	}
	// 求线段长度
	double length () { return s.distance (e); }
	//`返回直线倾斜角 0<=angle<pi`
	db angle () {
		db k = atan2 (e.y - s.y, e.x - s.x);
		if (sgn (k) < 0)
			k += pi;
		if (sgn (k - pi) == 0)
			k -= pi;
		return k;
	}
	//`点和直线关系`
	//`1  在左侧`点在线的逆时针
	//`2  在右侧`
	//`3  在直线上`
	int relation (Point p) {
		int c = sgn ((p - s) ^ (e - s));
		if (c < 0)
			return 1;
		else if (c > 0)
			return 2;
		else
			return 3;
	}
	// 点在线段上的判断
	bool pointonseg (Point p) {
		return sgn ((p - s) ^ (e - s)) == 0 && sgn ((p - s) * (p - e)) <= 0;
	}
	//`两向量平行(对应直线平行或重合)`
	bool parallel (Line v) { return sgn ((e - s) ^ (v.e - v.s)) == 0; }
	//`两线段相交判断`
	//`2 规范相交`
	//`1 非规范相交`
	//`0 不相交`
	int segcrossseg (Line v) {
		int d1 = sgn ((e - s) ^ (v.s - s));
		int d2 = sgn ((e - s) ^ (v.e - s));
		int d3 = sgn ((v.e - v.s) ^ (s - v.s));
		int d4 = sgn ((v.e - v.s) ^ (e - v.s));
		if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2)
			return 2;
		return (d1 == 0 && sgn ((v.s - s) * (v.s - e)) <= 0) ||
			   (d2 == 0 && sgn ((v.e - s) * (v.e - e)) <= 0) ||
			   (d3 == 0 && sgn ((s - v.s) * (s - v.e)) <= 0) ||
			   (d4 == 0 && sgn ((e - v.s) * (e - v.e)) <= 0);
	}
	//`直线和线段相交判断`
	//`-*this line   -v seg`
	//`2 规范相交`
	//`1 非规范相交`
	//`0 不相交`
	int linecrossseg (Line v) {
		int d1 = sgn ((e - s) ^ (v.s - s));
		int d2 = sgn ((e - s) ^ (v.e - s));
		if ((d1 ^ d2) == -2)
			return 2;
		return (d1 == 0 || d2 == 0);
	}
	//`两直线关系`
	//`0 平行`
	//`1 重合`
	//`2 相交`
	int linecrossline (Line v) {
		if ((*this).parallel (v))
			return v.relation (s) == 3;
		return 2;
	}
	//`求两直线的交点`
	//`要保证两直线不平行或重合`
	Point crosspoint (Line v) {
		db a1 = (v.e - v.s) ^ (s - v.s);
		db a2 = (v.e - v.s) ^ (e - v.s);
		return { (s.x * a2 - e.x * a1) / (a2 - a1),
				 (s.y * a2 - e.y * a1) / (a2 - a1) };
	}
	// 点到直线的距离
	db dispointtoline (Point p) { return fabs ((p - s) ^ (e - s)) / length (); }
	// 点到线段的距离
	db dispointtoseg (Point p) {
		if (sgn ((p - s) * (e - s)) < 0 || sgn ((p - e) * (s - e)) < 0)
			return min (p.distance (s), p.distance (e));
		return dispointtoline (p);
	}
	//`返回线段到线段的距离`
	//`前提是两线段不相交,相交距离就是0了`
	db dissegtoseg (Line v) {
		return min (min (dispointtoseg (v.s), dispointtoseg (v.e)),
					min (v.dispointtoseg (s), v.dispointtoseg (e)));
	}
	//`返回点p在直线上的投影`
	Point lineprog (Point p) {
		return s + (((e - s) * ((e - s) * (p - s))) / ((e - s).len2 ()));
	}
	//`返回点p关于直线的对称点`
	Point symmetrypoint (Point p) {
		Point q = lineprog (p);
		return { 2 * q.x - p.x, 2 * q.y - p.y };
	}
};
//***************************
// 圆
struct circle {
	Point p; // 圆心
	db r;    // 半径
	circle () {}
	circle (Point _p, db _r) {
		p = _p;
		r = _r;
	}
	circle (db x, db y, db _r) {
		p = Point (x, y);
		r = _r;
	}
	//`三角形的外接圆`
	//`需要Point的+ /  rotate()  以及Line的crosspoint()`
	//`利用两条边的中垂线得到圆心`
	//`测试:UVA12304`
	circle (Point a, Point b, Point c) {
		Line u = Line ((a + b) / 2, ((a + b) / 2) + ((b - a).rotleft ()));
		Line v = Line ((b + c) / 2, ((b + c) / 2) + ((c - b).rotleft ()));
		p = u.crosspoint (v);
		r = p.distance (a);
	}
	//`三角形的内切圆`
	//`参数bool t没有作用,只是为了和上面外接圆函数区别`
	//`测试:UVA12304`
	circle (Point a, Point b, Point c, bool t) {
		Line u, v;
		db m = atan2 (b.y - a.y, b.x - a.x), n = atan2 (c.y - a.y, c.x - a.x);
		u.s = a;
		u.e = u.s + Point (cos ((n + m) / 2), sin ((n + m) / 2));
		v.s = b;
		m = atan2 (a.y - b.y, a.x - b.x), n = atan2 (c.y - b.y, c.x - b.x);
		v.e = v.s + Point (cos ((n + m) / 2), sin ((n + m) / 2));
		p = u.crosspoint (v);
		r = Line (a, b).dispointtoseg (p);
	}
	// 输入
	void input () {
		p.input ();
		// scanf ("%lf", &r);
		cin >> r;
	}
	// 输出
	void output () {
		// printf ("%.2lf %.2lf %.2lf\n", p.x, p.y, r);
		cout << p.x << " " << p.y << " " << r << "\n";
	}
	bool operator== (circle v) { return (p == v.p) && sgn (r - v.r) == 0; }
	bool operator< (circle v) const {
		return ((p < v.p) || ((p == v.p) && sgn (r - v.r) < 0));
	}
	// 面积
	db area () { return pi * r * r; }
	// 周长
	db circumference () { return 2 * pi * r; }
	//`点和圆的关系`
	//`0 圆外`
	//`1 圆上`
	//`2 圆内`
	int relation (Point b) {
		db dst = b.distance (p);
		if (sgn (dst - r) < 0)
			return 2;
		else if (sgn (dst - r) == 0)
			return 1;
		return 0;
	}
	//`线段和圆的关系`
	//`比较的是圆心到线段的距离和半径的关系`
	int relationseg (Line v) {
		db dst = v.dispointtoseg (p);
		if (sgn (dst - r) < 0)
			return 2;
		else if (sgn (dst - r) == 0)
			return 1;
		return 0;
	}
	//`直线和圆的关系`
	//`比较的是圆心到直线的距离和半径的关系`
	int relationline (Line v) {
		db dst = v.dispointtoline (p);
		if (sgn (dst - r) < 0)
			return 2;
		else if (sgn (dst - r) == 0)
			return 1;
		return 0;
	}
	//`两圆的关系`
	//`5 相离`
	//`4 外切`
	//`3 相交`
	//`2 内切`
	//`1 内含`
	//`需要Point的distance`
	//`测试:UVA12304`
	int relationcircle (circle v) {
		db d = p.distance (v.p);
		if (sgn (d - r - v.r) > 0)
			return 5;
		if (sgn (d - r - v.r) == 0)
			return 4;
		db l = fabs (r - v.r);
		if (sgn (d - r - v.r) < 0 && sgn (d - l) > 0)
			return 3;
		if (sgn (d - l) == 0)
			return 2;
		if (sgn (d - l) < 0)
			return 1;
	}
	//`求两个圆的交点,返回0表示没有交点,返回1是一个交点,2是两个交点`
	//`需要relationcircle`
	//`测试:UVA12304`
	int pointcrosscircle (circle v, Point& p1, Point& p2) { // 两个圆不同
		int rel = relationcircle (v);
		if (rel == 1 || rel == 5)
			return 0;
		db d = p.distance (v.p);
		db l = (d * d + r * r - v.r * v.r) / (2 * d);
		db h = sqrt (r * r - l * l);
		Point tmp = p + (v.p - p).trunc (l);
		p1 = tmp + ((v.p - p).rotleft ().trunc (h));
		p2 = tmp + ((v.p - p).rotright ().trunc (h));
		if (rel == 2 || rel == 4)
			return 1;
		return 2;
	}
};

#define int long long

void output (vector<Point>& ans) {
	for (int i = 0; i < ans.size (); i++) {
		auto [x, y] = ans[i];
		long long ax, ay;
		int sign1 = 1, sign2 = 1;
		if (x < 0) {
			sign1 = -1;
			x = -x;
		}
		if (y < 0) {
			sign2 = -1;
			y = -y;
		}
		ax = x + 0.5, ay = y + 0.5;
		if (i != 0)
			cout << sign1 * ax << " " << sign2 * ay << " ";
		else
			cout << sign2 * ay << " ";
	}
}

signed main () {

	int A, B, C, D;
	cin >> A >> B >> C >> D;
	long double a = sqrt (A), b = sqrt (B), c = sqrt (C), d = sqrt (D);
	Point pa = Point (0, a);
	circle ob = circle (Point (0, 0), b);
	circle cc = circle (Point (a, 0), sqrt (2) * b);
	circle cd = circle (Point (a, a), b);

	circle oc = circle (Point (0, 0), c);
	circle od = circle (Point (0, 0), d);
	vector<Point> pj1 (2), pj2 (2);
	int num1 = 0, num2 = 0;
	num1 = cc.pointcrosscircle (oc, pj1[0], pj1[1]);
	num2 = cd.pointcrosscircle (od, pj2[0], pj2[1]);

	vector<Point> ans;
	for (int i = 0; i < num1; i++) {
		for (int j = 0; j < num2; j++) {
			Point pb = pa + pj1[i] - pj2[j];
			if (sgn (pb.len2 () - B) == 0) {
				ans.push_back (pa);
				ans.push_back (pb);
				ans.push_back (pj1[i]);
				ans.push_back (pj2[j]);
				output (ans);
				return 0;
			}
		}
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

36 5 10 41

output:

6 -2 1 3 -1 5 4 

result:

ok Answer is correct

Test #2:

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

input:

1 1 1 1

output:

1 -1 0 0 -1 1 0 

result:

ok Answer is correct

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3712kb

input:

1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

output:


result:

wrong output format Unexpected end of file - int64 expected