QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#783256#1196. Fun RegionJose_17WA 1ms4052kbC++2012.9kb2024-11-26 03:56:292024-11-26 03:56:29

Judging History

This is the latest submission verdict.

  • [2024-11-26 03:56:29]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 4052kb
  • [2024-11-26 03:56:29]
  • 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: 0ms
memory: 4052kb

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

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: -100
Wrong Answer
time: 0ms
memory: 3916kb

input:

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

output:

Error0

result:

wrong output format Expected double, but "Error0" found