QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#522850 | #6599. The Grand Tournament | SSL_TJH | WA | 1ms | 4100kb | C++14 | 6.4kb | 2024-08-17 16:00:22 | 2024-08-17 16:00:22 |
Judging History
answer
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#define cp const point &
#define cl const line &
#define LD long double
using namespace std;
const LD pi = acos(-1.0);
const LD eps = 1e-12;
int sgn(LD x) {
return x > eps ? 1 : (x < -eps ? -1 : 0);
}
struct point {
LD x, y;
point operator +(cp a) const {
return {x + a.x, y + a.y};
}
point operator -(cp a) const {
return {x - a.x, y - a.y};
}
point operator *(LD t) const {
return {x * t, y * t};
}
point operator /(LD t) const {
return {x / t, y / t};
}
point rot(LD t) const {
return {(LD) (x * cos(t) - y * sin(t)), (LD) {x * sin(t) + y * cos(t)}};
}
point rot90() const {
return {-y, x};
}
LD len2() const {
return x * x + y * y;
}
LD len() const {
return sqrtl(x * x + y * y);
}
point unit() const {
LD d = len();
return {(LD) (x / d), (LD) (y / d)};
}
int on_up() {
return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) < 0);
}
void print() {
cout << x << ' ' << y << endl;
}
void read() {
int xx, yy;
cin >> xx >> yy;
x = xx; y = yy;
}
friend bool operator < (cp a, cp b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
friend bool operator > (cp a, cp b) {
return a.x == b.x ? a.y > b.y : a.x > b.x;
}
};
LD dot(cp a, cp b);
bool operator==(cp a, cp b) {
return !sgn(dot(a - b, a - b));
}
bool operator!=(cp a, cp b) {
return !(a == b);
}
LD dot(cp a, cp b) {
return a.x * b.x + a.y * b.y;
}
LD det(cp a, cp b) {
return a.x * b.y - a.y * b.x;
}
struct line {
point s, t;
line()
{}
line(point a, point b) : s(a), t(b)
{}
void read() {
s.read(), t.read();
}
void print() {
s.print(), cout << ' ', t.print();
}
};
bool point_on_line(cp a, cl l) {
return sgn(det(a - l.s, l.t - l.s)) == 0;
}
bool point_on_segment(cp a, cl l) {
return point_on_line(a, l) && sgn(dot(l.s - a, l.t - a)) <= 0;
}
bool two_side(cp a, cp b, cl c) {
return sgn(det(a - c.s, c.t - c.s)) * sgn(det(b - c.s, c.t - c.s)) < 0;
}
bool intersect_judge_strict(cl a, cl b) {
return two_side(a.s, a.t, b) && two_side(b.s, b.t, a);
}
bool intersect_judge(cl a, cl b) {
if (point_on_segment(a.s, b) || point_on_segment(a.t, b) || point_on_segment(b.s, a) || point_on_segment(b.t, a)) return 1;
return intersect_judge_strict(a, b);
}
point line_intersect(cl a, cl b) {
LD s1 = det(a.t - a.s, b.s - a.s);
LD s2 = det(a.t - a.s, b.t - a.s);
return (b.s * s2 - b.t * s1) / (s2 - s1);
}
int onRight(cl a, cp b) {return det(a.t - a.s, b - a.s) <= -eps;}
vector <point> my_half_plane(vector <line> a) {
sort(a.begin(), a.end(), [&](line x, line y) {
point u = x.t - x.s, v = y.t - y.s;
if (u.on_up() != v.on_up()) return u.on_up() < v.on_up();
if (sgn(det(u, v))) return sgn(det(u, v)) > 0;
else return sgn(det(x.t - y.s, y.t - y.s)) < 0;
});
int n = a.size();
vector <line> que(n + 1);
vector <point> p1(n + 1);
vector <point> p2;
int left = 0, right = 0;
que[0] = a[0];
vector <point> sb;
for (int i = 1; i < n; i++) {
if (sgn(det(a[i].t - a[i].s, a[i - 1].t - a[i - 1].s)) == 0) continue;
while (left < right && onRight(a[i], p1[right])) right--;
while (left < right && onRight(a[i], p1[left + 1])) left++;
que[++right] = a[i];
if (std::abs(det(que[right].t - que[right].s, que[right - 1].t - que[right - 1].s)) <= eps) {
if (onRight(que[right], que[right - 1].s) && dot(que[right].t - que[right].s, que[right - 1].t - que[right - 1].s) <= -eps) return sb;
right--;
if (!onRight(que[right], a[i].s)) que[right] = a[i];
}
if (left < right) p1[right] = line_intersect(que[right], que[right - 1]);
}
while (left < right && onRight(que[left], p1[right])) right--;
if (right - left <= 1) return sb;
p1[left] = line_intersect(que[left], que[right]);
for (int i = left; i <= right; i++)
p2.push_back(p1[i]);
return p2;
}
LD get_are(vector <point> pu) {
LD ans = 0;
int n = pu.size();
for (int i = 0; i < n; i++) ans += det(pu[i], pu[(i + 1) % n]);
return ans / 2;
}
point l, r;
line l1, l2;
void slove() {
l.read(); r.read();
l1.read(); l2.read();
if (intersect_judge_strict(l1, l2) || !intersect_judge(l1, l2)) {
printf("0\n"); return ;
}
vector <line> f;
f.push_back(line(l, (point){r.x, l.y}));
f.push_back(line((point){r.x, l.y}, r));
f.push_back(line(r, (point){l.x, r.y}));
f.push_back(line((point){l.x, r.y}, l));
if (l1.t > l1.s) swap(l1.t, l1.s);
if (l2.t > l2.s) swap(l2.t, l2.s);
if ((l1.t - l1.s).len() < (l2.t - l2.s).len()) swap(l1, l2);
if (sgn(det(l1.t - l1.s, l2.t - l2.s)) == 0) {
int cnt = 0;
if (l1.s == l2.s) cnt++;
if (l1.s == l2.t) cnt++;
if (l1.t == l2.s) cnt++;
if (l1.t == l2.t) cnt++;
if (cnt == 2) {
printf("%.20Lf\n", (r.y - l.y) * (r.x - l.x)); return ;
}
else if (cnt == 1) {
if (!point_on_segment(l1.s, l2) || !point_on_segment(l1.t, l2)) {
printf("0\n"); return ;
}
if (l2.s == l1.s || l2.s == l1.t) {
f.push_back(line(l2.t, l2.t + (l2.t - l2.s).rot90()));
}
else {
f.push_back(line(l2.s, l2.s + (l2.s - l2.t).rot90()));
}
}
else if (!cnt) {
f.push_back(line(l1.t, l1.t + (l1.t - l1.s).rot90()));
f.push_back(line(l1.s, l1.s + (l1.s - l1.t).rot90()));
f.push_back(line(l2.t, l2.t + (l2.t - l2.s).rot90()));
f.push_back(line(l2.s, l2.s + (l2.s - l2.t).rot90()));
}
}
else {
if (l1.s != l2.s && l1.s != l2.t && l1.t != l2.s && l1.t != l2.t) {
printf("0\n"); return ;
}
point mt;
if (l1.s == l2.s || l1.s == l2.t) mt = l1.s;
else mt = l1.t;
if (l1.s != mt) swap(l1.s, l1.t);
if (l2.s != mt) swap(l2.s, l2.t);
f.push_back(line(l1.s, l1.s - (l1.s - l1.t).rot90()));
f.push_back(line(l2.s, l2.s - (l2.s - l2.t).rot90()));
}
printf("%.20Lf", get_are(my_half_plane(f)));
}
int main() {
int t; scanf("%d", &t);
while (t--) slove();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4100kb
input:
2 0 0 3 3 1 1 1 2 2 1 2 2 0 0 3 3 1 1 1 2 1 2 2 2
output:
0 1.00000000000000000000
result:
ok 2 numbers
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3804kb
input:
10 0 0 7 6 2 4 4 4 3 2 5 2 0 0 7 6 2 4 4 4 4 4 5 2 0 0 2 4 1 1 1 2 1 2 1 3 0 0 2 3 1 1 1 2 1 1 1 2 0 0 3 3 1 1 2 2 1 2 2 1 0 0 2 4 1 1 1 2 1 2 1 3 0 0 6 6 1 1 5 5 1 5 3 3 0 0 2 3 1 1 1 2 1 1 1 2 0 0 2 5 1 1 1 3 1 2 1 4 0 0 2 4 1 1 1 3 1 1 1 2
output:
0 3.750000000000000000000 6.00000000000000000000 0 0 0 6.00000000000000000000 2.000000000000000000000
result:
wrong answer 3rd numbers differ - expected: '0.0000000', found: '6.0000000', error = '6.0000000'