QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#513785 | #9168. Square Locator | ucup-team1074# | WA | 0ms | 3712kb | C++20 | 14.0kb | 2024-08-10 19:41:32 | 2024-08-10 19:41:34 |
Judging History
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