Submission #529087

#	Time	Username	Problem	Language	Result	Execution time	Memory
529087		8e7	Fences (JOI18_fences)	C++17	0 / 100	1 ms	204 KiB

fences

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b ){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define x first
#define y second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
pii vec(pii p, pii q) {return {q.x - p.x, q.y - p.y};}
ll dot(pii p, pii q){return p.x * q.x + p.y * q.y;}
ll cross(pii p, pii q){return p.x * q.y - p.y * q.x;}
int sgn(ll x){return (x > 0 ? 1 : (x == 0 ? 0 : -1));}
bool inl(pii p, pii l1, pii l2) {
	return cross(vec(p, l1), vec(p, l2)) == 0 && dot(vec(p, l1), vec(p, l2)) <= 0;
}
bool inter(pii p1, pii p2, pii q1, pii q2) {
	if (inl(p1, q1, q2) || inl(p2, q1, q2) || inl(q1, p1, p2) || inl(q2, p1, p2)) return 1;
	if (sgn(cross(vec(p1, q1), vec(p1, q2))) != sgn(cross(vec(p2, q1), vec(p2, q2))) &&
sgn(cross(vec(q1, p1), vec(q1, p2))) != sgn(cross(vec(q2, p1), vec(q2, p2)))) return 1;
	return 0;
}
ll sd(pii p, pii q){return (q.x - p.x) * (q.x - p.x) + (q.y - p.y) * (q.y - p.y);}
double getl(pii p){return sqrt(double(p.x * p.x + p.y * p.y));}
double dis(pii p, pii l1, pii l2) {
	pii vi = vec(l1, l2);
	if (sgn(cross(vi, vec(l1, p))) * sgn(cross(vi, vec(l2, p))) != 1) {
		double len = dot(p, vi) / getl(vi);
		return sqrt(double(sd(l1, p) - len * len));
	} else {
		ll mi = min(sd(p, l1), sd(p, l2));
		return sqrt(double(mi));
	}
}
double di[4];
int main() {
	io
	int n, s;
	cin >> n >> s;
	pii p1, p2;
	cin >> p1.x >> p1.y >> p2.x >> p2.y;
	pii q[4] = {{s, s}, {s, -s}, {-s, -s}, {-s, s}};
	bool valid[4] = {0, 0, 0, 0};

	double ans = 8 * s;	
	for (int i = 0;i < 4;i++) {
		pii vl = vec(q[i], p1), vr = vec(q[i], p2);
		pii wl = vec(q[(i+1)%4], q[(i+2)%4]), wr = vec(q[(i+1)%4], q[(i+2)%4]); 
		valid[i] = (!inter(q[i], p1,q[(i+1)%4], q[(i)%4]) && 
		!inter(q[i], p1, q[(i+1)%4], q[(i+2)%4])) || (!inter(q[i], p2, q[(i+1)%4], q[(i)%4]) && !inter(q[i], p2, q[(i+1)%4], q[(i+2)%4]));
		debug(i, valid[i]);
		di[i] = dis(q[i], p1, p2);
	}
	for (int i = 0;i < 4;i++) {
		if (valid[i] && valid[(i+1)%4]) {
			ans = min(ans, 6 * s + di[i] + di[(i+1)%4]);
		}
		if (valid[i] && valid[(i+2)%4]) {
			ans = min(ans, 4 * s + di[i] + di[(i+2)%4]);
		}
	}
	cout << fixed << setprecision(10) << ans << endl;
}

Compilation message (stderr)

fences.cpp: In function 'int main()':
fences.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
fences.cpp:62:3: note: in expansion of macro 'debug'
   62 |   debug(i, valid[i]);
      |   ^~~~~
fences.cpp:58:7: warning: variable 'vl' set but not used [-Wunused-but-set-variable]
   58 |   pii vl = vec(q[i], p1), vr = vec(q[i], p2);
      |       ^~
fences.cpp:58:27: warning: variable 'vr' set but not used [-Wunused-but-set-variable]
   58 |   pii vl = vec(q[i], p1), vr = vec(q[i], p2);
      |                           ^~
fences.cpp:59:7: warning: variable 'wl' set but not used [-Wunused-but-set-variable]
   59 |   pii wl = vec(q[(i+1)%4], q[(i+2)%4]), wr = vec(q[(i+1)%4], q[(i+2)%4]);
      |       ^~
fences.cpp:59:41: warning: variable 'wr' set but not used [-Wunused-but-set-variable]
   59 |   pii wl = vec(q[(i+1)%4], q[(i+2)%4]), wr = vec(q[(i+1)%4], q[(i+2)%4]);
      |                                         ^~

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