QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#522850#6599. The Grand TournamentSSL_TJHWA 1ms4100kbC++146.4kb2024-08-17 16:00:222024-08-17 16:00:22

Judging History

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

  • [2024-08-17 16:00:22]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4100kb
  • [2024-08-17 16:00:22]
  • 提交

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();
}

Details

Tip: Click on the bar to expand more detailed information

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'