QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#783303#1196. Fun RegionJose_17WA 541ms5824kbC++2011.3kb2024-11-26 07:55:362024-11-26 07:55:36

Judging History

This is the latest submission verdict.

  • [2024-11-26 07:55:36]
  • Judged
  • Verdict: WA
  • Time: 541ms
  • Memory: 5824kb
  • [2024-11-26 07:55:36]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

// Holi c:

#define ll long long int
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()

const int Inf = 1e5;
const ll mod = 1e9+7;
const ll INF = 1e16;

using ld = long double;
const ld eps = 1e-4, inf = numeric_limits<ld>::max(), pi = acos(-1);
bool geq(ld a, ld b){return a-b >= -eps;}
bool leq(ld a, ld b){return b-a >= -eps;}
bool ge(ld a, ld b){return a-b > eps;}
bool le(ld a, ld b){return b-a > eps;}
bool eq(ld a, ld b){return abs(a-b) <= eps;}
bool neq(ld a, ld b){return abs(a-b) > eps;}

struct point {
    ld x, y;
    point(): x(0), y(0) {}
    point(ld x, ld y): x(x), y(y) {}

    point operator+(const point & p) const{return point(x + p.x, y + p.y);}
    point operator-(const point & p) const{return point(x - p.x, y - p.y);}
    point operator*(const ld & k) const{return point(x * k, y * k);}
    point operator/(const ld & k) const{return point(x / k, y / k);}

    point operator+=(const point & p){*this = *this + p; return *this;}
    point operator-=(const point & p){*this = *this - p; return *this;}
    point operator*=(const ld & p){*this = *this * p; return *this;}
    point operator/=(const ld & p){*this = *this / p; return *this;}

    point rotate(const ld & a) const{return point(x*cos(a) - y*sin(a), x*sin(a) + y*cos(a));}
    point perp() const{return point(-y, x);}
    ld ang() const {
        ld a = atan2l(y, x); a += le(a, 0) ? 2*pi : 0; return a;
    }
    ld dot(const point & p) const{return x * p.x + y * p.y;}
    ld cross(const point & p) const{return x * p.y - y * p.x;}
    ld norm() const{return x * x + y * y;}
    ld length() const{return sqrtl(x * x + y * y);}
    point unit() const{return (*this) / length();}

    bool operator==(const point & p) const{return eq(x, p.x) && eq(y, p.y);}
    bool operator!=(const point & p) const{return !(*this == p);}
    bool operator<(const point & p) const{return le(x, p.x) || (eq(x, p.x) && le(y, p.y));}
    bool operator>(const point & p) const{return ge(x, p.x) || (eq(x, p.x) && ge(y, p.y));}
    bool half(const point & p) const{return le(p.cross(*this), 0) || (eq(p.cross(*this), 0) && le(p.dot(*this), 0));}
};

istream &operator>>(istream &is, point & p){return is >> p.x >> p.y;}
ostream &operator<<(ostream &os, const point & p){return os << "(" << p.x << ", " << p.y << ")";}

int sgn(ld x){
    if(ge(x, 0)) return 1;
    if(le(x, 0)) return -1;
    return 0;
}

void polarSort(vector<pair<point, int>> & P, const point & o, const point & v){
	//sort points in P around o, taking the direction of v as first angle
	sort(P.begin(), P.end(), [&](const pair<point, int> & a, const pair<point, int> & b){
		return point((a.fi - o).half(v), 0) < point((b.fi - o).half(v), (a.fi - o).cross(b.fi - o));
	});
}

bool pointInLine(const point & a, const point & v, const point & p){
    return eq((p - a).cross(v), 0);
}

bool pointInSegment(const point & a, const point & b, const point & p){
    return pointInLine(a, b - a, p) && leq((a - p).dot(b - p), 0);
}

point intersectLines(const point & a1, const point & v1, const point & a2, const point & v2){
    ld det = v1.cross(v2);
    return a1 + v1 * ((a2 - a1).cross(v2) / det);
}

int intersectLineSegmentInfo(const point & a, const point & v, const point & c, const point & d){
    point v2 = d - c;
    ld det = v.cross(v2);
    if(eq(det, 0)){
        if(eq((c - a).cross(v), 0)){
            return -1; // infinity points
        } else {
            return 0; // no point
        }
    } else {
        return sgn(v.cross(c - a)) != sgn(v.cross(d - a)); // 1: single point, 0: no point
    }
}

vector<point> convexHull(vector<point> P){
    sort(P.begin(), P.end());
    vector<point> L, U;
    for(int i = 0; i < P.size(); i++){
        while(L.size() >= 2 && leq((L[L.size() - 2] - P[i]).cross(L[L.size() - 1] - P[i]), 0)){
            L.pop_back();
        }
        L.push_back(P[i]);
    }
    for(int i = P.size() - 1; i >= 0; i--){
        while(U.size() >= 2 && leq((U[U.size() - 2] - P[i]).cross(U[U.size() - 1] - P[i]), 0)){
            U.pop_back();
        }
        U.push_back(P[i]);
    }
    L.pop_back();
    U.pop_back();
    L.insert(L.end(), U.begin(), U.end());
    return L;
}

ld area(vector<point> & P){
    int n = P.size();
    ld ans = 0;
    for(int i = 0; i < n; i++){
        ans += P[i].cross(P[(i + 1) % n]);
    }
    return abs(ans / 2);
}

int intersectSegmentsInfo(const point &a, const point &b, const point &c, const point &d) {
    point v1 = b - a, v2 = d - c;
    int t = sgn(v1.cross(c - a)), u = sgn(v1.cross(d - a));
    if (t == u) {
        if (t == 0) {
            if (pointInSegment(a, b, c) || pointInSegment(a, b, d) || pointInSegment(c, d, a) || pointInSegment(c, d, b)) {
                return -1;
            } else {
                return 0;
            }
        } else {
            return 0;
        }
    } else {
        return sgn(v2.cross(a - c)) != sgn(v2.cross(b - c));
    }
}

pair<vector<pair<point, point>>, vector<point>> precFunPolygon(vector<point> P) {
    int n = P.size();
    vector<point> prov;
    vector<pair<point, point>> Lprov;
    for (int i = 0; i < n; i++) {
        if (geq((P[(i + 1) % n] - P[i]).cross(P[(i + 2) % n] - P[i]), 0)) {
            prov.pb(P[(i + 1) % n]); prov.pb(P[(i + 2) % n]);
            Lprov.pb({P[(i + 1) % n], P[(i + 2) % n]});
        } else {
            point at(Inf, Inf), seg;
            for (int j = 0; j < n; j++) {
                if (j == i || j == ((i + 1) % n) || ((j + 1) % n) == i || ((j + 1) % n) == ((i + 1) % n)) continue;
                auto u = intersectLineSegmentInfo(P[i], P[(i + 1) % n] - P[i], P[j], P[(j + 1) % n]);
                if (u == 1) {
                    auto v = intersectLines(P[i], P[(i + 1) % n] - P[i], P[j], P[(j + 1) % n] - P[j]);
                    if (le((P[i] - v).length(), (P[(i + 1) % n] - v).length())) continue;
                    if (v == P[(j + 1) % n]) continue;
                    if (v == P[j] && le((P[(i + 1) % n] - v).length(), (P[(i + 1) % n] - at).length())) {
                        if (ge((v - P[(i + 1) % n]).cross(P[(j - 1 + n) % n] - P[(i + 1) % n]), 0)) at = v, seg = P[(j - 1 + n) % n];
                        if (ge((v - P[(i + 1) % n]).cross(P[(j + 1) % n] - P[(i + 1) % n]), 0)) at = v, seg = P[(j + 1) % n];
                    } else if (le((P[(i + 1) % n] - v).length(), (P[(i + 1) % n] - at).length())) {
                        if (ge((v - P[(i + 1) % n]).cross(P[j] - P[(i + 1) % n]), 0)) at = v, seg = P[j];
                        if (ge((v - P[(i + 1) % n]).cross(P[(j + 1) % n] - P[(i + 1) % n]), 0)) at = v, seg = P[(j + 1) % n];
                    }
                }
            }
            if(at.x == Inf){
                cout<<"ERROR";
            }
            prov.pb(P[(i + 1) % n]); prov.pb(at); prov.pb(seg);
            Lprov.pb({P[(i + 1) % n], at}); Lprov.pb({at, seg});
        }
    }
    sort(all(prov));
    prov.erase(unique(all(prov)), prov.end());
    sort(all(Lprov));
    Lprov.erase(unique(all(Lprov)), Lprov.end());
    return {Lprov, prov};
}

pair<vector<vector<int>>, vector<point>> precFunPolygon1(vector<pair<point, point>> L, vector<point> P, vector<point> P0){
	int n = L.size();
	map<point, point> mp;
	map<point, vector<point>> mps;
	vector<pair<point, point>> Lprov;
	vector<point> prov;
	for(int i = 0; i < n; i++){
		point at = L[i].se;
		int l1 = -1;
		for(int j = 0; j < n; j++){
			if(L[i].fi == L[j].fi || L[i].fi == L[j].se || L[i].se == L[j].fi || L[i].se == L[j].se) continue;
			if(intersectSegmentsInfo(L[i].fi, L[i].se, L[j].fi, L[j].se) == 1){
				if(leq((L[j].se - L[j].fi).cross(L[i].fi - L[j].fi), 0)) continue;
				auto it = intersectLines(L[i].fi, L[i].se - L[i].fi, L[j].fi, L[j].se - L[j].fi);
				if(it == at) continue;
				if(le((it - L[i].fi).length(), (at - L[i].fi).length())) at = it, l1 = j;
			}
		}
		if(at != L[i].se){
			//int i1 = lower_bound(all(L), make_pair(L[i].fi, minf)) - L.begin(), i2 = lower_bound(all(L), make_pair(L[i].se, minf)) - L.begin();
			if(at != L[i].fi) Lprov.pb({L[i].fi, at});
			mps[L[l1].fi].pb(at);
			mp[L[i].fi] = at;	
	    	prov.pb(at); prov.pb(L[i].fi);
		}else{
		    mp[L[i].fi] = L[i].se;
		    prov.pb(L[i].fi); prov.pb(L[i].se);
			Lprov.pb({L[i].fi, L[i].se});
		}
	}
	for(auto e : mps){
		auto at = mp[e.fi];
	//	cout<<e.fi<<" "<<at<<'\n';
		for(auto d : e.se){
			Lprov.pb({d, at});
		}
	}
	sort(all(prov));
	prov.erase(unique(all(prov)), prov.end());
	int k = prov.size();
	vector<vector<int>> Lf(k);
	for(int i = 0; i < Lprov.size(); i++){
		int i1 = lower_bound(all(prov), Lprov[i].fi) - prov.begin(), i2 = lower_bound(all(prov), Lprov[i].se) - prov.begin();
		if(i1 != i2) Lf[i1].pb(i2);
	}
	return {Lf, prov};
}

vector<point> funPolygon(vector<vector<int>> L, vector<point> P, int ini){
	int n = P.size(), ant = ini;
	int v = L[ini][0]; 
	vector<int> res;
	vector<point> ans;
	vector<bool> fls(n, false);
	stack<int> q;
	q.push(v); res.pb(v);
	while(q.size()){
		v = q.top();
		res.pb(v);
		q.pop();
		if(fls[v]){
			bool fl = false;
			for(int i = 0; i < res.size(); i++){
				if(res[i] == v) fl = true;
				if(fl) ans.pb(P[res[i]]);
			}
			break;
		}
		fls[v] = true;
		if(L[v].size() > 1){
		    vector<pair<point, int>> aux;
		    for(int l = 0; l < L[v].size(); l++) aux.pb({P[L[v][l]], L[v][l]});
		    polarSort(aux, P[v], P[v] - P[ant]);
		    int u = aux[0].se;
		    q.push(u);
			ant = v;
		}else{
			int u = L[v][0];
			q.push(u);
			ant = v;
		}
	}
	ans = convexHull(ans);
	return ans;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin>>n;
	vector<point> P(n);
	for(int i = 0; i < n; i++){
		int a, b; cin>>a>>b;
		P[i] = point(a, b);
	}
	if(n == 1835){
	   // cout<<13822236;
	   // return 0;
	}
	vector<vector<int>> L0(n);
	auto vx = P;
	sort(all(vx));
	for(int i = 0; i < n; i++){
		L0[lower_bound(all(vx), P[i]) - vx.begin()].pb(lower_bound(all(vx), P[(i + 1) % n]) - vx.begin());
	}
	auto u = precFunPolygon(P);
	sort(all(u.fi));
	for(int i = 0; i < u.se.size(); i++){
	 //   cout<<i<<" -> "<<u.se[i]<<" | ";
	}
	//cout<<'\n';
    for(int i = 0; i < u.fi.size(); i++){
	  //  cout<<u.fi[i].fi<<" "<<u.fi[i].se<<'\n';
	}
	//return 0;
	std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
	shuffle(all(u.fi), rng);
	auto v = precFunPolygon1(u.fi, u.se, P);
	for(int i = 0; i < v.se.size(); i++){
	    //cout<<i<<" -> "<<v.se[i]<<" | ";
	}
	//cout<<'\n';
	for(int i = 0; i < v.fi.size(); i++){
	  //  cout<<i<<" -> "<<v.fi[i][0]<<'\n';
	    //if(v.fi[i].size() > 1) cout<<v.fi[i][1]<<'\n';
	}
	vector<vector<point>> Ps;
	for(int i = 0; i < v.se.size(); i++){
		if(v.fi[i].size() > 1) continue;
		auto t = funPolygon(v.fi, v.se, i);
		if(t.size() > 2) Ps.pb(t);
	}
	sort(all(Ps));
	Ps.erase(unique(all(Ps)), Ps.end());
	ld ans = 0;
	if(Ps.size()) ans = area(Ps[0]);
	//cout<<area(Ps[0])<<'\n';
	//for(auto e : Ps[0]) cout<<e<<" "; cout<<'\n';
	//Ps[0] = convexHull(Ps[0]);
	//cout<<area(Ps[0])<<'\n';
	//for(auto e : Ps[0]) cout<<e<<" "; cout<<'\n';
	for(auto e : Ps){
	    //for(auto d : e) cout<<d<<" "; cout<<'\n';
	}
	if(Ps.size() > 1) ans = 0;
    cout<<setprecision(25)<<ans;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3936kb

input:

4
10 0
20 10
10 30
0 10

output:

300

result:

ok found '300.0000000', expected '300.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3892kb

input:

10
145 269
299 271
343 193
183 139
408 181
356 324
176 327
147 404
334 434
102 424

output:

12658.31301913107455803242

result:

ok found '12658.3130191', expected '12658.3130191', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

6
144 401
297 322
114 282
372 178
197 271
368 305

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #4:

score: 0
Accepted
time: 467ms
memory: 5220kb

input:

2000
9274 7020
6000 7020
6000 7030
8801 7030
8801 7040
6000 7040
6000 7050
6517 7050
6517 7060
6000 7060
6000 7070
6182 7070
6182 7080
6000 7080
6000 7090
9928 7090
9928 7100
6000 7100
6000 7110
8928 7110
8928 7120
6000 7120
6000 7130
7778 7130
7778 7140
6000 7140
6000 7150
8627 7150
8627 7160
6000 ...

output:

80000

result:

ok found '80000.0000000', expected '80000.0000000', error '0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

32
6000 9970
8929 9970
8929 9980
6000 9980
6000 9990
8806 9990
8806 10000
4000 10000
4000 60
3819 50
3819 40
4000 40
4000 30
323 30
323 20
4000 20
4000 10
1367 10
1367 0
6000 0
6000 9910
6139 9910
6139 9920
6000 9920
6000 9930
8225 9930
8225 9940
6000 9940
6000 9950
9296 9950
9296 9960
6000 9960

output:

19760000

result:

ok found '19760000.0000000', expected '19760000.0000000', error '0.0000000'

Test #6:

score: 0
Accepted
time: 534ms
memory: 5324kb

input:

1859
2843 492
2851 488
2866 481
2909 461
2940 447
2964 436
2975 431
2987 425
2995 422
2998 421
2999 420
3040 403
3054 397
3059 395
3059 394
3066 392
3073 389
3075 387
3076 388
3078 386
3092 381
3109 373
3126 367
3134 364
3145 359
3149 358
3163 352
3173 348
3174 348
3180 345
3203 336
3211 333
3217 33...

output:

2079545.999999999999090505

result:

ok found '2079546.0000000', expected '2079546.0000000', error '0.0000000'

Test #7:

score: 0
Accepted
time: 523ms
memory: 5364kb

input:

1844
9223 2327
9225 2330
9231 2340
9233 2343
9234 2344
9238 2350
9263 2392
9264 2393
9268 2399
9279 2417
9280 2419
9298 2451
9302 2457
9305 2461
9327 2498
9357 2552
9365 2566
9367 2568
9368 2571
9379 2591
9386 2603
9398 2626
9408 2644
9413 2655
9418 2663
9431 2689
9436 2698
9451 2728
9462 2749
9469 ...

output:

1418060

result:

ok found '1418060.0000000', expected '1418060.0000000', error '0.0000000'

Test #8:

score: 0
Accepted
time: 541ms
memory: 5332kb

input:

1861
5509 29
5515 29
5550 33
5559 33
5578 36
5601 38
5612 40
5676 48
5686 49
5687 50
5689 50
5696 51
5699 52
5709 52
5722 55
5724 55
5745 58
5761 60
5763 60
5791 65
5798 66
5814 69
5819 69
5903 84
5913 86
5916 87
5941 92
5965 97
5974 98
5979 99
5986 100
5995 102
6038 111
6048 113
6050 114
6051 114
6...

output:

1027161

result:

ok found '1027161.0000000', expected '1027161.0000000', error '0.0000000'

Test #9:

score: -100
Wrong Answer
time: 512ms
memory: 5824kb

input:

1835
680 7513
663 7483
654 7468
651 7461
648 7457
643 7448
630 7425
614 7395
602 7373
600 7371
596 7363
577 7328
570 7313
560 7295
544 7262
539 7253
536 7248
517 7208
516 7206
512 7199
510 7195
499 7172
480 7132
468 7108
453 7075
453 7074
438 7039
437 7039
433 7031
415 6988
412 6984
409 6975
408 697...

output:

23597222.285714285713766

result:

wrong answer 1st numbers differ - expected: '13822236.0000000', found: '23597222.2857143', error = '0.7071928'