Submission #1224944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224944		PenguinsAreCute	Fences (JOI18_fences)	C++17	0 / 100	0 ms	328 KiB

fences

#include <bits/stdc++.h>
using namespace std;
using ld = long double;
pair<ld,ld> nearest(int a, int b, int c, int d, int x, int y) {
	pair<ld,ld> ln1 = {(d-b)/ld(c-a), 0};
	ln1.second = b - ln1.first * a;
	pair<ld,ld> ln2 = {-1/ln1.first,0};
	ln2.second = y - ln2.first * x;
	pair<ld,ld> isect = {0,0};
	isect.first = (ln2.second - ln1.second) / (ln1.first - ln2.first);
	if(isect.first < a && isect.first < c)
		isect.first = min(a, c);
	if(isect.first > a && isect.first > c)
		isect.first = max(a, c);
	isect.second = ln1.first * isect.first + ln1.second;
	return isect;
}
ld dist(pair<ld,ld> a, pair<ld,ld> b) {return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));}
int main() {
	int n, s, a, b, c, d;
	cin >> n >> s;
	cin >> a >> b >> c >> d;
	if(a == c || b == d) {
		cout << 8 * s;
		return 0;
	}
	pair<ld,ld> st[4] = {{s,s},{-s,s},{-s,-s},{s,-s}};
	pair<ld,ld> p[4];
	for(int i=0;i<4;i++) {
		p[i] = nearest(a,b,c,d,st[i].first,st[i].second);
		if(p[i].first / st[i].first <= 1 && p[i].second / st[i].second <= 1)
			p[i] = {1e9,0};
	}
	ld ans = 0;
	for(int i=0;i<4;i++)
		ans = min(ans,dist(st[i],p[i])+dist(st[(i+1)&3],p[(i+1)&3])-2*s);
	for(int i=0;i<2;i++)
		ans = min(ans,dist(st[i],p[i])+dist(st[(i+2)&3],p[(i+2)&3])-4*s);
	cout << fixed << setprecision(10) << ans+8*s;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 33
• Subtask 3: 0 / 49