Slant Drilling

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

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	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;
		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;
		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++;
		if (cnt%2 && ala < minA) {
			minA=ala;
			inH=h2;
		}
		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 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED