QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#345535#7734. Intersection over UnionSortingTL 6ms4076kbC++204.5kb2024-03-07 05:38:472024-03-07 05:38:47

Judging History

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

  • [2024-03-07 05:38:47]
  • 评测
  • 测评结果:TL
  • 用时:6ms
  • 内存:4076kb
  • [2024-03-07 05:38:47]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <stack>
#include <utility>
#include <iomanip>

using namespace std;
typedef double ld;

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
	friend ostream& operator<<(ostream& os, P p) {
		return os << "(" << p.x << "," << p.y << ")"; }
};
typedef Point<ld> P;
template<class T>
T polygonArea2(const vector<Point<T>> &v) {
	T a = v.back().cross(v[0]);
	for(int i = 0; i < (int)v.size() - 1; ++i) a += v[i].cross(v[i+1]);
	return a;
}

pair<int, P> lineInter(P s1, P e1, P s2, P e2) {
	auto d = (e1 - s1).cross(e2 - s2);
	auto p = s2.cross(e1, e2), q = s2.cross(e2, s1);
	return {1, (s1 * p + e1 * q) / d};
}

void polygonCut(const vector<P>& poly, P s, P e, vector<P> &res) {
    res.clear();
	for(int i = 0; i < poly.size(); ++i){
		P cur = poly[i], prev = i ? poly[i-1] : poly.back();
		bool side = s.cross(e, cur) < 0;
		if (side != (s.cross(e, prev) < 0))
			res.push_back(lineInter(s, e, cur, prev).second);
		if (side)
			res.push_back(cur);
	}
}

const ld EPS = 1e-9;
P p[4];
P center;
ld area;
vector<P> v;

ld calc(ld x, ld y){
    // cout << "calc " << x << " " << y << endl;
    vector<P> our;
    our.push_back(P{center.x - x, center.y - y});
    our.push_back(P{center.x + x, center.y - y});
    our.push_back(P{center.x + x, center.y + y});
    our.push_back(P{center.x - x, center.y + y});

    // cout << center.x << " " << center.y << "\n";

    vector<P> swp;
    for(int i = 0; i < 4; ++i){
        // cout << i << " i" << endl;
        int prv = (i + 4 - 1) % 4;
        polygonCut(our, v[i], v[prv], swp);
        swap(swp, our);
        // cout << our.size() << " size here" << endl;
    }
    // cout << our.size() << " size" << endl;

    ld inters_area = abs(polygonArea2(our)) / 2;
    ld added_area = 4 * x * y - inters_area;
    
    return inters_area / (added_area + area);
}

ld search_y(ld x){
    ld r = (sqrt((ld)5) - 1) / 2;
    ld a = 0, b = 1e9;
    ld x1 = b - r*(b-a), x2 = a + r*(b-a);
	ld f1 = calc(x, x1), f2 = calc(x, x2);
    while((b - a) > EPS){
        if(f1 > f2){
        	b = x2; x2 = x1; f2 = f1;
			x1 = b - r*(b-a); f1 = calc(x, x1);
		} else {
			a = x1; x1 = x2; f1 = f2;
			x2 = a + r*(b-a); f2 = calc(x, x2);
		}
    }
    return calc(x, a);
}

ld search_x(){
    ld r = (sqrt((ld)5) - 1) / 2;
    ld a = 0, b = 1e9;
    ld x1 = b - r*(b-a), x2 = a + r*(b-a);
	ld f1 = search_y(x1), f2 = search_y(x2);
    while((b - a) > EPS){
        if(f1 > f2){
        	b = x2; x2 = x1; f2 = f1;
			x1 = b - r*(b-a); f1 = search_y(x1);
		} else {
			a = x1; x1 = x2; f1 = f2;
			x2 = a + r*(b-a); f2 = search_y(x2);
		}
    }
    return search_y(a);
}

void solve(){
    for(int i = 0; i < 4; ++i){
        int x, y;
        cin >> x >> y;
        p[i] = P{(ld)x, (ld)y};
    }

    v = vector<P>(p, p + 4);

    area = polygonArea2(v);
    if(area < 0){
        reverse(p, p + 4);
        reverse(v.begin(), v.end());
        area = -area;
    }
    area /= 2;

    center = (p[0] + p[1] + p[2] + p[3]) / 4;
    cout << fixed << setprecision(12) <<  search_x() << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while(t--){
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 4076kb

input:

3
0 2 2 0 0 -2 -2 0
7 -2 9 -2 9 2 7 2
7 13 11 10 5 2 1 5

output:

0.707106781187
0.999999999406
0.623843224831

result:

ok 3 numbers

Test #2:

score: -100
Time Limit Exceeded

input:

10000
-568767734 379152673 -565681345 -54946093 -131582579 -51859704 -134668968 382239062
-194884120 -559906233 -194884142 -158042604 -998611400 -158042648 -998611378 -559906277
459335966 -945199065 478030260 -934243779 450535683 -887326546 431841389 -898281832
-483567491 491964356 -523827401 408140...

output:


result: