QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#863114#9728. Catch the StarJose_17WA 200ms4096kbC++1413.8kb2025-01-19 13:21:092025-01-19 13:21:10

Judging History

This is the latest submission verdict.

  • [2025-01-19 13:21:10]
  • Judged
  • Verdict: WA
  • Time: 200ms
  • Memory: 4096kb
  • [2025-01-19 13:21:09]
  • 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 = 1e9;
const int Inf2 = 1e9 + 1;
const ll mod = 1e9+7;
const ll INF = 4e18;
const ll INF2 = 1e10 + 1;
 
using ld = long double;
const ld eps = 1e-6, 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;
}

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

vector<vector<point>> twoSidesCH(vector<point> P){
	sort(P.begin(), P.end());
	vector<vector<point>> L;
	vector<point> U;
	for(int i = 0; i < P.size(); 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]);
	}
	if(eq(U[U.size() - 1].x, U[U.size() - 2].x)) U.pop_back();
	L.pb(U);
	U.clear();
	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]);
	}
	reverse(all(U));
	if(eq(U[U.size() - 1].x, U[U.size() - 2].x)) U.pop_back();
	reverse(all(U));
	if(eq(U[U.size() - 1].x, U[U.size() - 2].x)) U.pop_back();
	L.pb(U);
	return L;
}

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

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

int intersectSegmentsInfo(const point & a, const point & b, const point & c, const point & d){
	//segment ab, segment cd
	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; //infinity points
			}else{
				return 0; //no point
			}
		}else{
			return 0; //no point
		}
	}else{
		return sgn(v2.cross(a - c)) != sgn(v2.cross(b - c)); //1: single point, 0: no point
	}
}

bool pointInPerimeter(const vector<point> & P, const point & p){
	int n = P.size();
	for(int i = 0; i < n; i++){
		if(pointInSegment(P[i], P[(i + 1) % n], p)){
			return true;
		}
	}
	return false;
}

bool crossesRay(const point & a, const point & b, const point & p){
	return (geq(b.y, p.y) - geq(a.y, p.y)) * sgn((a - p).cross(b - p)) > 0;
}

int pointInPolygon(const vector<point> & P, const point & p){
	if(pointInPerimeter(P, p)){
		return 1;
	}
	int n = P.size();
	int rays = 0;
	for(int i = 0; i < n; i++){
		rays += crossesRay(P[i], P[(i + 1) % n], p);
	}
	return rays & 1;
}

vector<point> tangentsPointPolygon(const vector<point> & P, const vector<vector<point>> & Ps, const point & p, const vector<vector<point>> & T, const vector<vector<int>> & Ls, const vector<point> & B){
	for(int i = 0; i < T.size(); i++){
		if(pointInPolygon(T[i], p)){
		    return {T[i][1], T[i][0]}; 
		}
	}

	int n = P.size(), m = Ps[0].size(), k = Ps[1].size();

	auto tang = [&](int l, int r, const vector<point> & A, ld w) -> int {
		int res = l;
		int y = A.size();
        while(l <= r){
            int m = (l + r) / 2;
			ld a = (A[m] - p).cross(A[(m + 1) % y] - p) * w, b = (A[m] - p).cross(A[(m - 1 + y) % y] - p) * w;
			if(geq(a, 0) && geq(b, 0)) return m;
            if(geq(a, 0)) r = m - 1, res = m;
            else l = m + 1;
        }
        return res;
    };

	auto bs = [&](int l, int r, const vector<point> & A, ld w) -> int {
        int res = l;
        ld w1 = p.x * w;
        while(l <= r){
            int m = (l + r) / 2;
			if(ge(A[m].x * w, w1)) r = m - 1;
			else res = max(res, m), l = m + 1;
        }
        return res;
    };

	point left = p, rigth = p;
	point f1 = Ps[0][0], f2 = Ps[0][m - 1];
	if(neq((P[Ls[0][1]] - P[Ls[0][0]]).cross(P[Ls[1][1]] - P[Ls[1][0]]), 0)){
	    auto yh = intersectLines(P[Ls[0][0]], P[Ls[0][1]] - P[Ls[0][0]], P[Ls[1][0]], P[Ls[1][1]] - P[Ls[1][0]]);
	    if(yh.x < f1.x) f1 = yh;
	}
	if(neq((P[Ls[2][1]] - P[Ls[2][0]]).cross(P[Ls[3][1]] - P[Ls[3][0]]), 0)){
	    auto yh = intersectLines(P[Ls[2][0]], P[Ls[2][1]] - P[Ls[2][0]], P[Ls[3][0]], P[Ls[3][1]] - P[Ls[3][0]]);
	    if(yh.x > f2.x) f2 = yh;
	}
	//cout<<f1<<f2<<'\n';
	//cout<<P[Ls[0][0]]<<" , "<<P[Ls[0][1]]<<" | "<<P[Ls[1][0]]<<" , "<<P[Ls[1][1]]<<" | "<<P[Ls[2][0]]<<" , "<<P[Ls[2][1]]<<" | "<<P[Ls[3][0]]<<" , "<<P[Ls[3][1]]<<'\n';
	if(geq((P[Ls[0][1]] - P[Ls[0][0]]).cross(p - P[Ls[0][0]]), 0) && geq((P[Ls[1][1]]- P[Ls[1][0]]).cross(p - P[Ls[1][0]]), 0) && Ls[0][0] != Ls[0][1]){
		left = Ps[1][tang(0, k - 1, Ps[1], -1)];
		rigth = Ps[0][tang(0, m - 1, Ps[0], 1)];
	}else if(geq((P[Ls[2][1]] - P[Ls[2][0]]).cross(p - P[Ls[2][0]]), 0) && geq((P[Ls[3][1]]- P[Ls[3][0]]).cross(p - P[Ls[3][0]]), 0) && Ls[2][0] != Ls[2][1]){
		left = Ps[0][tang(0, m - 1, Ps[0], -1)];
		rigth = Ps[1][tang(0, k - 1, Ps[1], 1)];
	}else if(le((f2 - f1).cross(p - f1), 0)){
		int t = bs(0, m - 1, Ps[0], 1);
		if(leq((Ps[1][k - 1] - p).cross(Ps[0][0] - p), 0) && leq((Ps[1][k - 1] - p).cross(Ps[1][k - 2] - p), 0) && leq((Ps[1][k - 1] - p).cross(Ps[0][1] - p), 0)) left = Ps[1][k - 1];
		else left = Ps[0][tang(0, min(t, m - 2), Ps[0], -1)];
		if(geq((Ps[1][0] - p).cross(Ps[0][m - 1] - p), 0) && geq((Ps[1][0] - p).cross(Ps[1][1] - p), 0) && geq((Ps[1][0] - p).cross(Ps[0][m - 2] - p), 0)) rigth = Ps[1][0];
		else rigth = Ps[0][tang(min(t + 1, m - 1), m - 1, Ps[0], 1)];
	}else if(ge((f2 - f1).cross(p - f1), 0)){
		int t = bs(0, k - 1, Ps[1], -1);
		if(leq((Ps[0][m - 1] - p).cross(Ps[1][0] - p), 0) && leq((Ps[0][m - 1] - p).cross(Ps[0][m - 2] - p), 0) && leq((Ps[0][m - 1] - p).cross(Ps[1][1] - p), 0)) left = Ps[0][m - 1];
		else left = Ps[1][tang(0, min(t, k - 2), Ps[1], -1)];
		if(geq((Ps[0][0] - p).cross(Ps[1][k - 1] - p), 0) && geq((Ps[0][0] - p).cross(Ps[1][k - 2] - p), 0) && geq((Ps[0][0] - p).cross(Ps[0][1] - p), 0)) rigth = Ps[0][0];
		else rigth = Ps[1][tang(min(t + 1, k - 1), k - 1, Ps[1], 1)];
	}else{
	  //  cout<<"C";
	    int i = lower_bound(all(Ps[0]), p) - Ps[0].begin();
	    int j = lower_bound(all(B), p) - B.begin();
	    if(pointInSegment(Ps[0][i], Ps[0][i - 1], p)) left = Ps[0][i - 1], rigth = Ps[0][i];
	    if(pointInSegment(B[j], B[j - 1], p)) left = B[j], rigth = B[j - 1];
	}
	return {left, rigth};
}

pair<vector<vector<point>>, vector<vector<int>>> precTangents(vector<point> P){
	int n = P.size();
	auto R = twoSidesCH(P);
	int m = R[0].size(), k = R[1].size();
	bool f1 = false, f2 = false;
	int il1 = 0, il2 = 0, sl1 = 0, sl2 = 0, ir1 = 0, ir2 = 0, sr1 = 0, sr2 = 0;
	il1 = 1; il2 = 0; sl1 = 0; sl2 = n - 1;
	ir1 = m - 1; ir2 = m - 2; sr1 = m % n; sr2 = m - 1;
	if(R[0][m - 1] != R[1][0]) sr1 = (sr1 + 1) % n, sr2 = (sr2 + 1) % n;
	if(R[0][0] != R[1][k - 1]) sl1 = n - 1, sl2 = n - 2;
	point a(-INF2, -1000), b(-INF2, 1000);
	vector<vector<point>> Ts;
	if(il2 != sl1){
		if(eq((P[il2] - P[il1]).cross(P[sl2] - P[sl1]), 0)){
			auto it = intersectLines(P[il1], P[il2] - P[il1], a, b - a), at = intersectLines(P[sl1], P[sl2] - P[sl1], a, b - a);
			Ts.pb({P[il2], P[sl1], at, it});
			il1 = il2 = sl1 = sl2 = -1;
		}else{
			auto it = intersectLines(P[il1], P[il2] - P[il1], P[sl1], P[sl2] - P[sl1]);
			if(ge(it.x, P[il1].x)){
				auto it = intersectLines(P[il1], P[il2] - P[il1], a, b - a), at = intersectLines(P[sl1], P[sl2] - P[sl1], a, b - a);
				Ts.pb({P[il2], P[sl1], at, it});
				il1 = il2 = sl1 = sl2 = -1;
			}else{
				Ts.pb({P[il2], P[sl1], it});
			}
		}
	}
	a = point(INF2, -1000); b = point(INF2, 1000);
	if(sr2 != ir1){
		if(eq((P[ir2] - P[ir1]).cross(P[sr2] - P[sr1]), 0)){
			auto it = intersectLines(P[ir1], P[ir2] - P[ir1], a, b - a), at = intersectLines(P[sr1], P[sr2] - P[sr1], a, b - a);
			Ts.pb({P[sr2], P[ir1], it, at});
			ir1 = ir2 = sr1 = sr2 = -1;
		}else{
			auto it = intersectLines(P[ir1], P[ir2] - P[ir1], P[sr1], P[sr2] - P[sr1]);
			if(le(it.x, P[ir1].x)){
				auto it = intersectLines(P[ir1], P[ir2] - P[ir1], a, b - a), at = intersectLines(P[sr1], P[sr2] - P[sr1], a, b - a);
				Ts.pb({P[sr2], P[ir1], it, at});
				ir1 = ir2 = sr1 = sr2 = -1;
			}else{
				Ts.pb({P[sr2], P[ir1], it});
			}
		}
	}
	return {Ts, {{il1, il2}, {sl1, sl2}, {ir1, ir2}, {sr1, sr2}}};
}

pair<ld, ld> calc(vector<point> & A, vector<point> B, pair<vector<vector<point>>, vector<vector<int>>> & zw, vector<vector<point>> & tws, vector<point> & tw){
    ld minx = INF, maxx = -INF;
    point x0(-Inf2, 0), x1(Inf2, 0);
    int n = B.size();
    for(int i = 0; i < n; i++){
        auto u = intersectSegmentsInfo(B[i], B[(i + 1) % n], x0, x1);
        if(u == 1){
            auto p = intersectLines(B[i], B[(i + 1) % n] - B[i], x0, x1 - x0);
            minx = min(minx, p.x); maxx = max(maxx, p.x);
        }else if(u == -1){
            minx = min(minx, min(B[i].x, B[(i + 1) % n].x));
            maxx = max(maxx, max(B[i].x, B[(i + 1) % n].x));
        }
    }
    point a1(1000, 0);
    for(int i = 0; i < n; i++){
        auto ts = tangentsPointPolygon(A, tws, B[i], zw.fi, zw.se, tw);
        point t1 = ts[0], t2 = ts[1];
        //cout<<t1<<" "<<t2<<'\n';
        if(neq(a1.cross(t1 - B[i]), 0)){
            auto p = intersectLines(B[i], t1 - B[i], point(0, 0), a1);
            if(eq((p - t1).length(), (p - B[i]).length() + (B[i] - t1).length())){
                minx = min(minx, p.x); maxx = max(maxx, p.x);
            }
        }
        if(neq(a1.cross(t2 - B[i]), 0)){
            auto p = intersectLines(B[i], t2 - B[i], point(0, 0), a1);
            if(eq((p - t2).length(), (p - B[i]).length() + (B[i] - t2).length())){
                minx = min(minx, p.x); maxx = max(maxx, p.x);
            }
        }
    }
    return {minx, maxx};
}

ld calc(){
    int m, l, r; cin>>m>>l>>r;
    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);
    }
    vector<vector<point>> Moons;
    for(int i = 0; i < m; i++){
        int k; cin>>k; vector<point> aux;
        for(int j = 0; j < k; j++){
            int a, b; cin>>a>>b; aux.pb(point(a, b));
        }
        Moons.pb(aux);
    }

    auto zw = precTangents(P);
	auto tws = twoSidesCH(P);
	auto tw = tws[1]; sort(all(tw));
	//for(auto e : tws[0]) cout<<e<<" "; cout<<'\n';
	//for(auto e : tw) cout<<e<<" "; cout<<'\n';

    vector<pair<ld, ld>> Segs;
    for(int i = 0; i < m; i++){
        auto u = calc(P, Moons[i], zw, tws, tw);
        Segs.pb(u);
    }
    sort(all(Segs));
    //for(auto e : Segs) cout<<e.fi<<" - "<<e.se<<" | "; cout<<'\n';
    ld ans = 0, ant = l; bool f = false;
    for(int i = 0; i < m; i++){
        if(Segs[i].fi > r){
            ant = Segs[i].fi; break;
        }
        if(Segs[i].fi >= ant){
            if(!((Segs[i].fi == l && ant == l) || (Segs[i].fi == r && ant == r))) f = true; 
            ans += (Segs[i].fi - ant);
        }
        ant = max(ant, Segs[i].se);
    }
    if(ant < r){
        f = true; ans += r - ant;
    }
    if(!f) return -1;
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t; cin>>t;
    while(t--){
        cout<<setprecision(25)<<calc()<<'\n';
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 4096kb

input:

2
4 -8 8
3 -7 7 -6 8 -7 8
3 -9 -2 -7 3 -9 -1
3 -2 3 0 2 -4 5
3 5 1 5 3 4 2
3 1 -1 2 -2 3 -1
5 -8 8
5 -14 -3 -10 -2 -9 2 -10 4 -12 5
3 -16 0 -15 0 -15 1
3 -15 6 -9 5 -15 7
3 -10 5 -9 5 -10 6
3 -7 3 -3 2 -8 4
3 -6 -1 -6 -2 -5 -1

output:

9.404761904761904761987368
6

result:

ok 2 numbers

Test #2:

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

input:

3
1 -4 4
3 -2 6 0 5 2 6
3 -3 1 3 1 0 4
3 -2 2
3 -2 4 2 4 0 6
3 -2 2 -1 2 -2 3
3 1 2 2 2 2 3
3 -2 -1 0 -3 2 -1
1 1 2
3 -8 0 -7 0 -8 1
3 -5 0 -4 -1 -4 0

output:

-1
0
1

result:

ok 3 numbers

Test #3:

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

input:

1
1 -744567334 955216804
5 -781518205 -852078097 -781516900 -852078384 -781516392 -852076569 -781518329 -852076047 -781519925 -852077600
5 -393011614 -131855702 -393010699 -131856607 -393008846 -131856475 -393009388 -131854587 -393010201 -131854694

output:

1699779738.691979192313738

result:

ok found '1699779738.691979170', expected '1699779738.691979170', error '0.000000000'

Test #4:

score: -100
Wrong Answer
time: 200ms
memory: 4096kb

input:

16666
2 -732787031 -732787030
3 -798263477 735869144 -583647039 529057159 -583647039 529057160
3 -777230180 499482549 -777230181 499482549 -777230180 499482548
3 -661853868 251627327 -661853868 251627326 -661853867 251627327
2 463140451 463140452
3 232604219 637008523 797038205 345997813 797038205 3...

output:

0
0
0
0
-1
0
0
2.910383045673370361328125e-11
1.455191522836685180664062e-11
-1
1.455191522836685180664062e-11
0
0
0
7.275957614183425903320312e-12
5.82076609134674072265625e-11
1.455191522836685180664062e-11
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1.455191522836685180664062e-11
0
-1
0
5.8207660913467407...

result:

wrong answer 1st numbers differ - expected: '-1.0000000', found: '0.0000000', error = '1.0000000'