QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#702811 | #6639. Disk Tree | stavage | WA | 4ms | 13256kb | C++20 | 2.1kb | 2024-11-02 16:37:14 | 2024-11-02 16:37:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
#define int LL
#define double LD
const int N = 2e5 + 5;
const double eps = 1e-8;
const double PI = acosl(-1);
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
};
typedef Point Vector;
Point operator+(Point a, Point b) { return Point(a.x + b.x, a.y + b.y); }
Point operator-(Point a, Point b) { return Point(a.x - b.x, a.y - b.y); }
Point operator*(Point a, double p) { return Point(a.x * p, a.y * p); }
Point operator/(Point a, double p) { return Point(a.x / p, a.y / p); }
bool operator<(const Point &a, const Point &b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
int sgn(double x)
{
if (fabs(x) < eps) return 0;
if (x < 0) return -1;
return 1;
}
bool operator==(const Point &a, const Point &b) { return !sgn(a.x - b.x) && !sgn(a.y - b.y); }
struct Circle {
Point c;
double r;
Circle(Point c = Point(), double r = 0) : c(c), r(r) {}
inline Point point(double a)
{
return Point(c.x + cos(a) * r, c.y * sin(a) * r);
}
bool operator<(const Circle a) const { return c < a.c; }
};
inline Circle read_circle()
{
Circle c;
cin >> c.c.x >> c.c.y >> c.r;
return c;
}
double xmult(Point p1, Point p2, Point p0)
{
return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
Circle c[N];
void solve()
{
int f = -1;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
c[i] = read_circle();
if (c[i].c.x - c[i].r < 0) f = 1;
else if (c[i].c.x + c[i].r > 1e9)
f = 0;
}
if (!f) {
cout << "NO\n";
return;
}
cout << "YES\n";
sort(c, c + n);
for (int i = 1; i < n; i++) {
cout << c[i - 1].c.x + f * c[i - 1].r << " " << c[i - 1].c.y << " " << c[i].c.x + f * c[i].r << " " << c[i].c.y << "\n";
}
}
signed main()
{
cin.tie(nullptr)->ios::sync_with_stdio(false);
cout << fixed << setprecision(0);
int _ = 1;
while (_--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 13256kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 1 5 4 0 4 0 16 10
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 4ms
memory: 13060kb
input:
2 1 1 1 3 3 1
output:
YES 0 1 2 3
result:
ok answer = 1
Test #3:
score: -100
Wrong Answer
time: 4ms
memory: 13252kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 1 0 2 20 2 20 0 10 0 10 19 0 19 0 19 20
result:
wrong answer Two line segments intersect, and it's not only the endpoints that intersect or line segments intersects/touches more than 2 disks