Submission details
Task:Slant Drilling
Sender:Game of Nolife
Submission time:2015-11-25 20:12:28 +0200
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#2ACCEPTED0.05 sdetails
#3ACCEPTED0.05 sdetails
#4ACCEPTED0.11 sdetails
#5ACCEPTED0.05 sdetails
#6ACCEPTED0.06 sdetails
#7ACCEPTED0.05 sdetails
#8ACCEPTED0.05 sdetails
#9ACCEPTED0.06 sdetails

Code

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> co;

const ld INF=1e15;

ld dist(co a, co b, ld h) {
	ld lol;
	if (((a/(b-a)).X)*((b/(b-a)).X) >0) lol=min(abs(a),abs(b));
	else lol=abs(b-a)*((a/(b-a)).Y);
	return sqrt(lol*lol+h*h);
}

int sgnCr(co a, co b) {
	if (a.X*b.Y-a.Y*b.X < 0) return -1;
	return 1;
}

int inct(co a, co b, co c, co d) {
	if (sgnCr(b-a,c-a)*sgnCr(b-a,d-a) > 0) return 0;
	if (sgnCr(d-c,a-c)*sgnCr(d-c,b-c) > 0) return 0;
	return 1;
}

co p[101010];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
//	n=1;
	ld parsaDist=INF;
	ld minA=INF;
	ld inH=INF;
	ld maxA=0;
	ld outH=INF;
	for (int j=0;j<n;j++) {
		ld h1, h2;
		cin>>h1>>h2;
//		h1=50;
//		h2=42;
		int m;
		cin>>m;
//		co p[101010];
		for (int i=0;i<m;i++) {
			ld x,y;
			cin>>x>>y;
			p[i]={x,y};
		}
		ld ala=0;
		for (int i=1;i<m;i++) {
			ala+=(p[i].X-p[i-1].X)*(p[i].Y+p[i-1].Y)/2;
		}
		ala+=(p[0].X-p[m-1].X)*(p[0].Y+p[m-1].Y)/2;
		ala=abs(ala);
//		cout<<ala<<"\n";
		if (ala>maxA) {
			maxA=ala;
			outH=h1;
		}
		int cnt=0;
		for (int i=1;i<m;i++) {
			if (inct({0,0},{1e9+7,1},p[i-1],p[i])) cnt++;
		}
		if (inct({0,0},{1e9+7,1},p[m-1],p[0])) cnt++;
//		cout<<cnt<<endl;
		if (cnt%2 && ala < minA) {
			minA=ala;
			inH=h2;
//			cout<<minA<<endl;
		}
		for (int i=1;i<m;i++) {
			parsaDist=min(parsaDist,dist(p[i-1],p[i],min(h1,h2)));
		}
		parsaDist=min(parsaDist,dist(p[m-1],p[0],min(h1,h2)));
	}
	if (minA<INF) {
		parsaDist=min(parsaDist,inH);
	} else {
		parsaDist=min(parsaDist,outH);
	}
	cout<<setprecision(15)<<parsaDist<<"\n";
}

Test details

Test 1

Verdict: ACCEPTED

input
3
0 10 5 -270 0 -90 -450 270 -45...

correct output
10.0000000000

user output
10

Test 2

Verdict: ACCEPTED

input
3
75 100 27 0 -10 0 -5 5 -5 5 5 ...

correct output
40.5253956465

user output
40.5253956465288

Test 3

Verdict: ACCEPTED

input
3
75 100 27 0 -10 0 -5 5 -5 5 5 ...

correct output
50

user output
50

Test 4

Verdict: ACCEPTED

input
25000
99996 100000 4 -1 -1 1 -1 1 1 ...

correct output
70707.8497481008

user output
70707.8497481008

Test 5

Verdict: ACCEPTED

input
6
42 10000 10 -90 -90 -90 90 90 ...

correct output
42.0000000000

user output
42

Test 6

Verdict: ACCEPTED

input
2
15 30 3 1 -999998 1 999999 -1 ...

correct output
15.0000000000

user output
15

Test 7

Verdict: ACCEPTED

input
1
30 31 3 0 -7 1 20 -1 20

correct output
30.0011187006

user output
30.001118700603

Test 8

Verdict: ACCEPTED

input
1
5 4 10000 -24995 0 -24985 10 -...

correct output
4.0000000000

user output
4

Test 9

Verdict: ACCEPTED

input
1
5 4 20 -45 0 -35 10 -25 0 -15 ...

correct output
4.0000000000

user output
4