QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#783257#1196. Fun RegionJose_17TL 1ms4040kbC++2012.9kb2024-11-26 03:57:182024-11-26 03:57:18

Judging History

This is the latest submission verdict.

  • [2024-11-26 03:57:18]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 4040kb
  • [2024-11-26 03:57:18]
  • 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()

typedef long long int ll;

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

using ld = long double;
//const ld eps = 1e-9, inf = numeric_limits<ld>::max(), pi = acos(-1);

struct fraccion{
	ll num, den;
	fraccion(){
		num = 0, den = 1;
	}
	fraccion(ll x, ll y){
		if(y < 0)
			x *= -1, y *=-1;
		ll d = __gcd(abs(x), abs(y));
		num = x/d, den = y/d;
	}
	fraccion(ll v){
		num = v;
		den = 1;
	}
	fraccion operator+(const fraccion& f) const{
		ll d = __gcd(den, f.den);
		return fraccion(num*(f.den/d) + f.num*(den/d), den*(f.den/d));
	}
	fraccion operator-() const{
		return fraccion(-num, den);
	}
	fraccion operator-(const fraccion& f) const{
		return *this + (-f);
	}
	fraccion operator*(const fraccion& f) const{
		return fraccion(num*f.num, den*f.den);
	}
	fraccion operator/(const fraccion& f) const{
		return fraccion(num*f.den, den*f.num);
	}
	fraccion operator+=(const fraccion& f){
		*this = *this + f;
		return *this;
	}
	fraccion operator-=(const fraccion& f){
		*this = *this - f;
		return *this;
	}
	fraccion operator++(int xd){
		*this = *this + 1;
		return *this;
	}
	fraccion operator--(int xd){
		*this = *this - 1;
		return *this;
	}
	fraccion operator*=(const fraccion& f){
		*this = *this * f;
		return *this;
	}
	fraccion operator/=(const fraccion& f){
		*this = *this / f;
		return *this;
	}
	bool operator==(const fraccion& f) const{
		ll d = __gcd(den, f.den);
		return (num*(f.den/d) == (den/d)*f.num);
	}
	bool operator!=(const fraccion& f) const{
		ll d = __gcd(den, f.den);
		return (num*(f.den/d) != (den/d)*f.num);
	}
	bool operator >(const fraccion& f) const{
		ll d = __gcd(den, f.den);
		return (num*(f.den/d) > (den/d)*f.num);
	}
	bool operator <(const fraccion& f) const{
		ll d = __gcd(den, f.den);
		return (num*(f.den/d) < (den/d)*f.num);
	}
	bool operator >=(const fraccion& f) const{
		ll d = __gcd(den, f.den);
		return (num*(f.den/d) >= (den/d)*f.num);
	}
	bool operator <=(const fraccion& f) const{
		ll d = __gcd(den, f.den);
		return (num*(f.den/d) <= (den/d)*f.num);
	}
	fraccion inverso() const{
		return fraccion(den, num);
	}
	fraccion fabs() const{
		fraccion nueva;
		nueva.num = abs(num);
		nueva.den = den;
		return nueva;
	}
	long double value() const{
		return (long double)num / (long double)den;
	}
};

bool geq(fraccion a, fraccion b){return a >= b;}
bool leq(fraccion a, fraccion b){return a <= b;}
bool ge(fraccion a, fraccion b){return a > b;}
bool le(fraccion a, fraccion b){return a < b;}
bool eq(fraccion a, fraccion b){return a == b;}
bool neq(fraccion a, fraccion b){return a != b;}

struct point {
    fraccion x, y;
    point(): x(fraccion()), y(fraccion()) {}
    point(fraccion x, fraccion 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 fraccion & k) const{return point(x * k, y * k);}
    point operator/(const fraccion & 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 fraccion & p){*this = *this * p; return *this;}
    point operator/=(const fraccion & p){*this = *this / p; return *this;}

    fraccion dot(const point & p) const{return x * p.x + y * p.y;}
    fraccion cross(const point & p) const{return x * p.y - y * p.x;}
    fraccion norm() const{return x * x + y * y;}

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

int sgn(fraccion x){
    if(ge(x, fraccion(0))) return 1;
    if(le(x, fraccion(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), fraccion());
}

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

point intersectLines(const point & a1, const point & v1, const point & a2, const point & v2){
    fraccion 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;
    fraccion det = v.cross(v2);
    if(eq(det, fraccion(0))){
        if(eq((c - a).cross(v), fraccion(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++){
        auto s = P[i].cross(P[(i + 1) % n]);
		ans += s.value();
    }
    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]), fraccion())) {
            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(fraccion(Inf), fraccion(Inf + 1)), 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).norm(), (P[(i + 1) % n] - v).norm())) continue;
                    if(v == P[(j + 1) % n]) continue;
                    if(v == P[j] && le((P[(i + 1) % n] - v).norm(), (P[(i + 1) % n] - at).norm())){
                        if(ge((v - P[(i + 1) % n]).cross(P[(j - 1 + n) % n] - P[(i + 1) % n]), fraccion())) at = v, seg = P[(j - 1 + n) % n];
                        if(ge((v - P[(i + 1) % n]).cross(P[(j + 1) % n] - P[(i + 1) % n]), fraccion())) at = v, seg = P[(j + 1) % n];
                    }else if(le((P[(i + 1) % n] - v).norm(), (P[(i + 1) % n] - at).norm())) {
                        if(ge((v - P[(i + 1) % n]).cross(P[j] - P[(i + 1) % n]), fraccion())) at = v, seg = P[j];
                        if(ge((v - P[(i + 1) % n]).cross(P[(j + 1) % n] - P[(i + 1) % n]), fraccion())) at = v, seg = P[(j + 1) % n];
                    }
                }
            }
            if(at.x == Inf && at.y == Inf + 1){
                //cout<<"Error";
                return {};
            }
            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){
	int n = L.size();
	map<point, point> mp;
	map<point, vector<point>> mps;
	vector<pair<point, point>> Lprov;
	vector<point> prov;
	point minf(-Inf, -Inf);
	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).norm(), (at - L[i].fi).norm())) 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;
		//cout<<a<<" "<<b<<'\n';
		P[i] = point(fraccion(a), fraccion(b));
	}
	//for(auto e : P) cout<<e<<" "; cout<<'\n';
	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;
	auto v = precFunPolygon1(u.fi, u.se);
	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<<" -> "; if(v.fi[i].size()) cout<<v.fi[i][0]; cout<<'\n';
	    //if(v.fi[i].size() > 1) cout<<v.fi[i][1]<<'\n';
	}
	vector<vector<point>> Ps;
	for(int i = 0; i < v.fi.size(); i++){
		if(v.fi[i].size() > 1 || v.fi[i].size() == 0) 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]);
	for(auto e : Ps){
	    //for(auto d : e) cout<<d.x.value()<<" "<<d.y.value()<<" | "; cout<<'\n';
	}
	if(Ps.size() > 1) ans = 0;
    cout<<setprecision(25)<<ans;
}

详细

Test #1:

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

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: 3836kb

input:

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

output:

12658.31301913107456158514

result:

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

Test #3:

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

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: -100
Time Limit Exceeded

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:


result: