QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#31728 | #21645. 是男人就得80分问题 | Qingyu | 10 | 1ms | 4332kb | C++20 | 6.0kb | 2022-05-11 23:24:09 | 2022-05-11 23:24:10 |
Judging History
answer
//2016 ACM-ICPC World Finals Problem. H
//O(n^4 log n)
//Extremely hard to code!!!
#include<bits/stdc++.h>
using namespace std;
#define ld double
#define eps 1e-5
struct vec{
ld x , y; vec(ld _x = 0 , ld _y = 0) : x(_x) , y(_y){}
friend vec operator +(vec p , vec q){return vec(p.x + q.x , p.y + q.y);}
friend vec operator -(vec p , vec q){return vec(p.x - q.x , p.y - q.y);}
friend ld operator *(vec p , vec q){return p.x * q.x + p.y * q.y;}
friend ld operator %(vec p , vec q){return p.x * q.y - p.y * q.x;}
friend vec rot(vec x , ld a){return vec(x.x * cos(a) - x.y * sin(a) , x.x * sin(a) + x.y * cos(a));}
friend ld ang(vec p){return atan2(p.y , p.x);}
friend ld len(vec p){return sqrt(p.x * p.x + p.y * p.y);}
friend bool operator <(vec p , vec q){return fabs(p.y - q.y) < eps ? p.x < q.x : p.y < q.y;}
}A[53] , B[53] , TA[53] , TB[53]; int NA , NB;
struct line{
vec s , t; ld ag; line(vec _s = vec() , vec _t = vec() , bool f = 0) : s(_s) , t(_t){if(f) ag = ang(_t - _s);}
friend bool truesect(line p , line q){
if(((q.t - p.s) % (p.t - p.s)) * ((q.s - p.s) % (p.t - p.s)) > -eps) return 0;
swap(p , q); if(((q.t - p.s) % (p.t - p.s)) * ((q.s - p.s) % (p.t - p.s)) > -eps) return 0;
return 1;
}
};
ld move(vec s , vec t , vec q){return (fabs(s.x - t.x) < eps ? s.x : s.x + (q.y - s.y) / (t.y - s.y) * (t.x - s.x)) - q.x;}
int p , q , r , sz; bool vis[53];
int nxt(int x){while(vis[(x - 1) % sz + 1]) ++x; return (x - 1) % sz + 1;}
bool check(vec *v){
bool f = (v[r] - v[q]) % (v[q] - v[p]) > -eps;
for(int i = 1 ; i <= sz ; ++i){
f &= (v[i] - v[p]) % (v[q] - v[p]) < eps || (v[i] - v[q]) % (v[r] - v[q]) < eps || (v[i] - v[r]) % (v[p] - v[r]) < eps;
}
int x = nxt(1) , y = nxt(x + 1) , pre = x;
do{
f &= !truesect(line(v[x] , v[y]) , line(v[p] , v[r]));
x = y; y = nxt(y + 1);
}while(x != pre);
return !f;
}
struct tri{vec x[3]; vec& operator [](int p){return x[p];}}; vector < tri > trA , trB;
vector < tri > prepare_triangulation(vec *v , int sz){
vector < tri > tmp; p = 1; q = 2; r = 3; ::sz = sz; memset(vis , 0 , sizeof(vis));
for(int i = 1 ; i <= sz - 2 ; ++i){
while(check(v)){p = q; q = r; r = nxt(r + 1);}
tmp.push_back((tri){v[p] , v[q] , v[r]}); vis[q] = 1; q = r; r = nxt(r + 1);
}
return tmp;
}
struct dat{ld pos , inc1 , inc2;}; ld ans;
bool operator <(dat p , dat q){if(fabs(p.pos - q.pos) < eps){return p.inc2 > q.inc2;} return p.pos < q.pos;}
void work(ld agp , ld agq , ld dlty){
vector < dat > pot; ld lsum = 0;
for(int k = 1 ; k <= NA + 1 ; ++k) TA[k] = rot(A[k] , -agp);
for(int k = 1 ; k <= NB + 1 ; ++k) TB[k] = rot(B[k] , -agq) - vec(0 , dlty);
for(int k = 1 ; k <= NA ; ++k)
for(int l = 1 ; l <= NB ; ++l){
vec xa = TA[k] , xb = TA[k + 1] , ya = TB[l] , yb = TB[l + 1] , x = xb - xa , y = yb - ya;
if(fabs(x % y) < eps)
if(fabs(x.y) < eps){
if(fabs(xa.y - ya.y) > eps) continue;
if(x.x < 0){swap(xa , xb); x.x = -x.x;} if(y.x < 0){swap(ya , yb); y.x = -y.x;}
ld minl = min(x.x , y.x); lsum += minl;
pot.push_back((dat){ya.x - xb.x , 1 , 0}); pot.push_back((dat){ya.x - xb.x + minl , -1 , 0});
pot.push_back((dat){yb.x - xa.x , 1 , 0}); pot.push_back((dat){yb.x - xa.x - minl , -1 , 0});
}else{
ld dlt = move(ya , yb , xa); xa.x += dlt; xb.x += dlt;
if(x.y < 0){swap(xa , xb);} if(y.y < 0){swap(ya , yb);}
ld l = max((ld)0 , min(xb.y , yb.y) - max(xa.y , ya.y)) / fabs(x.y) * len(x); lsum += l;
pot.push_back((dat){dlt , 0 , l}); pot.push_back((dat){dlt , 0 , -l});
}
}
vector < tri > tA = trA , tB = trB;
for(auto &x : tA) for(int i = 0 ; i < 3 ; ++i) x[i] = rot(x[i] , -agp);
for(auto &x : tB) for(int i = 0 ; i < 3 ; ++i) x[i] = rot(x[i] , -agq) - vec(0 , dlty);
vector < dat > pt1;
for(auto l : tA){
for(int i = 0 ; i < 3 ; ++i){l[i].x = -l[i].x; l[i].y = -l[i].y;}
int mxl = 0; for(int i = 0 ; i < 3 ; ++i) if(l[mxl] < l[i]) mxl = i;
for(int i = 0 ; i < mxl ; ++i){swap(l[0] , l[2]); swap(l[0] , l[1]);}
for(auto r : tB){
int mxr = 0; for(int i = 0 ; i < 3 ; ++i) if(r[mxr] < r[i]) mxr = i;
for(int i = 0 ; i < mxr ; ++i){swap(r[0] , r[2]); swap(r[0] , r[1]);}
vec fir = l[0] + r[0]; int pl = 0 , pr = 0; vector < ld > pt; bool f1 = 0 , f2 = 0;
while(pl < 3 || pr < 3){
vec nw;
if(pr == 3 || (pl < 3 && (l[(pl + 1) % 3] - l[pl]) % (r[(pr + 1) % 3] - r[pr]) <= 0)){
nw = fir + (l[(pl + 1) % 3] - l[pl]); ++pl;
}else{nw = fir + (r[(pr + 1) % 3] - r[pr]); ++pr;}
if(nw.y * fir.y <= eps) pt.push_back(fabs(nw.y - fir.y) < eps ? nw.x : nw.x + -nw.y / (fir.y - nw.y) * (fir.x - nw.x));
fir = nw; f1 |= nw.y > eps; f2 |= nw.y < -eps;
}
sort(pt.begin() , pt.end());
if(f1 && f2 && pt.size() >= 2 && pt.back() - pt[0] > eps){
pt1.push_back((dat){pt[0] , 0 , -1}); pt1.push_back((dat){pt.back() , 0 , 1});
}
}
}
sort(pt1.begin() , pt1.end()); sort(pot.begin() , pot.end()); ld v1 = 0 , v2 = 0; int cnt = 0 , p1 = 0 , pt = 0;
while(pt < pot.size()){
ld cur = min(pot[pt].pos , p1 < pt1.size() ? pt1[p1].pos : 1e18);
bool f = !cnt; while(p1 < pt1.size() && pt1[p1].pos < cur + eps) f |= !(cnt += pt1[p1++].inc2);
if(f){ans = max(ans , v1 * cur + v2);}
while(pt < pot.size() && fabs(pot[pt].pos - cur) < eps){
dat t = pot[pt++]; v2 += t.inc2; v1 += t.inc1; v2 += -t.inc1 * t.pos;
if(f){ans = max(ans , v1 * t.pos + v2);}
}
}
}
int main(){
cin >> NA; for(int i = 1 ; i <= NA ; ++i) cin >> A[i].x >> A[i].y;
cin >> NB; for(int i = 1 ; i <= NB ; ++i) cin >> B[i].x >> B[i].y;
assert(std::max(NA,NB)<=3);
A[NA + 1] =A[1]; B[NB + 1] = B[1]; trA = prepare_triangulation(A , NA); trB = prepare_triangulation(B , NB);
for(int i = 1 ; i <= NA ; ++i)
for(int j = 1 ; j <= NB ; ++j){
ld agp = ang(A[i + 1] - A[i]) , agq = ang(B[j + 1] - B[j]);
work(agp , agq , rot(B[j] , -agq).y - rot(A[i] , -agp).y);
work(agp , agq + acos(-1) , rot(B[j] , -agq - acos(-1)).y - rot(A[i] , -agp).y);
}
cout << fixed << setprecision(4) << ans; return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 1ms
memory: 4332kb
input:
3 40 0 0 0 0 30 3 10 0 0 -40 -10 0
output:
41.2311
result:
ok found '41.23110', expected '41.23106', error '0.00000'
Test #2:
score: 0
Dangerous Syscalls
input:
4 -20 0 0 20 20 0 0 -20 4 15 15 15 -15 -15 -15 -15 15
output:
result:
Test #3:
score: 0
Dangerous Syscalls
input:
8 0 0 0 1 1 100 1 1 2 100 2 1 3 100 3 0 8 100 0 99 0 0 1 99 1 0 2 99 2 0 3 100 3
output:
result:
Test #4:
score: 0
Dangerous Syscalls
input:
8 0 0 50 0 50 -10 30 -10 30 -50 20 -50 20 -10 0 -10 8 0 50 50 100 70 80 40 50 50 40 80 70 100 50 50 0
output:
result:
Test #5:
score: 0
Dangerous Syscalls
input:
24 0 0 5 5 5 0 10 5 10 0 15 5 15 0 20 5 20 0 25 5 25 0 30 5 30 0 35 5 35 0 40 5 40 0 45 5 45 0 50 5 50 0 55 5 55 -1 0 -1 24 0 0 5 5 5 0 10 5 10 0 15 5 15 0 20 5 20 0 25 5 25 0 30 5 30 0 35 5 35 0 40 5 40 0 45 5 45 0 50 5 50 0 55 5 55 -1 0 -1
output:
result:
Test #6:
score: 0
Dangerous Syscalls
input:
16 -1 2 0 1 1 2 1 1 2 1 1 0 2 -1 1 -1 1 -2 0 -1 -1 -2 -1 -1 -2 -1 -1 0 -2 1 -1 1 16 5 40 20 30 30 20 40 5 40 -5 30 -20 20 -30 5 -40 -5 -40 -20 -30 -30 -20 -40 -5 -40 5 -30 20 -20 30 -5 40
output:
result:
Test #7:
score: 0
Dangerous Syscalls
input:
11 6 0 4 0 0 10 0 20 10 20 20 22 20 -50 15 -50 14 -17 15 10 10 10 11 6 0 4 0 0 10 0 20 15 30 30 35 27 -7 20 -50 20 24 10 20 10 10
output:
result:
Test #8:
score: 0
Dangerous Syscalls
input:
11 0 0 -50 0 -50 10 -49 10 -49 3 -20 3 -20 4 49 4 49 10 50 10 50 1 6 0 0 0 1 60 61 61 61 61 60 1 0
output:
result:
Test #9:
score: 0
Dangerous Syscalls
input:
50 0 10 2 11 4 10 6 11 8 10 10 11 12 10 14 11 16 10 18 11 20 10 22 11 24 10 26 11 28 10 30 11 32 10 34 11 38 10 40 11 42 10 44 11 48 10 49 11 49 0 47 1 45 0 43 1 41 0 39 1 37 0 35 1 33 0 31 1 29 0 25 1 23 0 21 1 19 0 17 1 15 0 13 1 11 0 9 1 7 0 6 1 5 0 3 1 1 0 0 0 50 0 10 2 11 4 10 6 11 8 10 10 11 1...
output:
result:
Test #10:
score: 0
Dangerous Syscalls
input:
49 -25 -10 -24 -23 -32 -9 -29 -48 -39 -68 -22 -79 -24 -53 -16 -82 13 -94 9 -42 9 -27 5 -30 4 -57 -7 -54 -16 -32 -20 20 -11 18 -6 -47 -6 -52 2 -56 3 -29 13 -24 15 -35 19 -87 21 -88 17 -36 60 15 33 11 31 37 32 59 21 52 25 0 -5 -10 -7 16 13 41 -17 51 -20 90 -39 77 -35 25 -40 35 -37 -4 -44 77 -19 92 33 ...