Breaking Biscuits

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long  double ld;
ld dot(pair<ld, ld> a, pair<ld, ld> b) {
	return a.F*b.F + a.S*b.S;
}
pair<ld, ld> miinus(pair<ld, ld> a, pair<ld, ld> b) {
	return {a.F-b.F, a.S-b.S};
}

int main() {
	int b;
	cin>>b;
	vector<pair<ld, ld> > v(b);
	for(int i = 0; i < b; ++i) {
		cin>>v[i].F>>v[i].S;
	}
	ld ans = 1e9;
	for(int i = 0; i < b; ++i) {
		for(int j = i+1; j < b; ++j) {
			auto w = miinus(v[j], v[i]);
			ld z1 = 0;
			ld z2 = 0;
			for(int k = 0; k < b; ++k) {
				auto w2 = miinus(v[k], v[i]);
				ld q = dot(w2, w)/dot(w, w);
				auto w3 = make_pair(q*w.F, q*w.S);
				auto w4 = miinus(w2, w3);
				if(dot(make_pair(w.S, -w.F), w4) >= 0) {
					z1 = max(z1, sqrt(dot(w4, w4)));
				}
				else {
					z2 = max(z2, sqrt(dot(w4, w4)));
				}
			}
			ans = min(ans, z1+z2);
		}
	}
	cout<<fixed<<setprecision(15)<<ans<<endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED