QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#863114 | #9728. Catch the Star | Jose_17 | WA | 200ms | 4096kb | C++14 | 13.8kb | 2025-01-19 13:21:09 | 2025-01-19 13:21:10 |
Judging History
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'