QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#31728#21645. 是男人就得80分问题Qingyu10 1ms4332kbC++206.0kb2022-05-11 23:24:092022-05-11 23:24:10

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-11 23:24:10]
  • 评测
  • 测评结果:10
  • 用时:1ms
  • 内存:4332kb
  • [2022-05-11 23:24:09]
  • 提交

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 ...

output:


result: