Submission #529116

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

fences

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int, int> pii;
#define pb emplace_back
#define AI(x) begin(x),end(x)
#define ff first
#define ss second
#ifdef OWO
#define debug(args...) LKJ("\033[0;32m[ " + string(#args) + " ]\033[0m", args)
template <class I> void LKJ(I&&x) { cerr << x << endl; }
template <class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template <class I> void OI(I a, I b) { while (a < b) cerr << *a << " \n"[next(a) == b]; }
#else
#define debug(...) 0
#define OI(...) 0
#endif

const double eps = 1e-8;
struct Vec {
	double x, y;
	Vec(double _x = 0, double _y = 0): x(_x), y(_y) {}
	const Vec operator + (const Vec& o) const { return Vec(x + o.x, y + o.y); }
	const Vec operator - (const Vec& o) const { return Vec(x - o.x, y - o.y); }
	const Vec operator * (const double& m) const { return Vec(x * m, y * m); }
	const bool operator != (const Vec& o) const { return fabs(x - o.x) > eps or fabs(y - o.y) > eps; }
	const Vec T() const { return Vec(y, -x); }
};
struct Seg {
	Vec a, b;
	Seg() = default;
	Seg(Vec _a, Vec _b): a(_a), b(_b) {}
	Seg(double _a, double _b, double _c, double _d): a(_a, _b), b(_c, _d) {}
	const Vec getVec() const { return Vec(b.x - a.x, b.y - a.y); }
};
double dot(const Vec& a, const Vec& b)
{ return a.x * b.x + a.y * b.y; }
double cross(const Vec& a, const Vec& b)
{ return a.x * b.y - a.y * b.x; }
double abs2(const Vec& a)
{ return a.x * a.x + a.y * a.y; }
double abs(const Vec& a)
{ return sqrt(a.x * a.x + a.y * a.y); }
double getDist(const Vec& a, const Vec& b)
{ return sqrt(abs2(b - a)); }
double getLen(const Seg& s)
{ return sqrt(abs2(s.getVec())); }
bool getHalf(const Vec& a)
{ return a.y > eps or (fabs(a.y) <= eps and a.x > eps); }
int sgn(double a) { return (a > eps) - (a < -eps); }
bool on(const Vec& v, const Seg& s) {
	Vec a = s.a - v;
	Vec b = s.b - v;
	debug(a.x, a.y, b.x, b.y, sgn(cross(a, b)), sgn(dot(a, b)));
	return sgn(cross(a, b)) == 0 and sgn(dot(a, b)) < 0;
}
bool intersect(const Seg& a, const Seg& b) {
	int c123 = sgn(cross(a.b - a.a, b.a - a.a));
	int c124 = sgn(cross(a.b - a.a, b.b - a.a));
	int c341 = sgn(cross(b.b - b.a, a.a - b.a));
	int c342 = sgn(cross(b.b - b.a, a.b - b.a));
	return (c123 * c124 < 0 and c341 * c342 < 0);
}

const int kN = 101;
const int kP = kN * 3;
int N, S;
Seg segs[kN], edge[4];
Vec pts[kP];

const double INF = 1e18;

bool crossed_pasture(Seg s) {
	for (int i = 0; i < 4; ++i)
		if (intersect(s, Seg(pts[i], pts[(i + 1) % 4]))) return true;
	if (intersect(s, Seg(S, S, -S, -S))) return true;
	if (intersect(s, Seg(-S, S, S, -S))) return true;
	return on(Vec(0, 0), s);
}
bool has_T(Vec v, Seg s) {
	Vec a = s.a - v;
	Vec b = s.b - v;
	return fabs(cross(a, b) <= eps) and sgn(dot(a, b)) < 0;
}
double to(Vec a, Vec b) {
	Seg s(a, b);
	double len = crossed_pasture(s) ? INF : abs(b - a);
	debug(a.x, a.y, b.x, b.y, len);
	return len;
}
double to(int p, Seg s) {
	double len = INF;
	Vec v = pts[p];
	len = min(len, to(pts[p], s.a));
	len = min(len, to(pts[p], s.b));
	if (has_T(v, s)) {
		Vec to_T = s.getVec().T();
		to_T = to_T * (cross(s.b - v, s.a - v) / abs2(s.getVec()));
		if (!crossed_pasture(Seg(pts[p], pts[p] + to_T)))
			len = min(len, abs(to_T));
	}
	return len;
}
double go(int a, int b, Seg seg) {
	return to(a, seg) + to(b, seg);
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> S;

	Seg seg;
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		seg = Seg(a, b, c, d);
	}

	pts[0] = Vec( S, S);
	pts[1] = Vec( S,-S);
	pts[2] = Vec(-S,-S);
	pts[3] = Vec(-S, S);

	double ans = 8 * S;
	ans = min(ans, go(0, 1, seg) + 6 * S);
	debug(ans);
	ans = min(ans, go(1, 2, seg) + 6 * S);
	debug(ans);
	ans = min(ans, go(2, 3, seg) + 6 * S);
	debug(ans);
	ans = min(ans, go(3, 0, seg) + 6 * S);
	debug(ans);
	ans = min(ans, go(0, 2, seg) + 4 * S);
	debug(ans);
	ans = min(ans, go(1, 3, seg) + 4 * S);
	debug(ans);
	cout << setprecision(12) << fixed << ans << '\n';
	return 0;
}

Compilation message (stderr)

fences.cpp: In function 'bool on(const Vec&, const Seg&)':
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
fences.cpp:53:2: note: in expansion of macro 'debug'
   53 |  debug(a.x, a.y, b.x, b.y, sgn(cross(a, b)), sgn(dot(a, b)));
      |  ^~~~~
fences.cpp: In function 'double to(Vec, Vec)':
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
fences.cpp:87:2: note: in expansion of macro 'debug'
   87 |  debug(a.x, a.y, b.x, b.y, len);
      |  ^~~~~
fences.cpp: In function 'int main()':
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
fences.cpp:126:2: note: in expansion of macro 'debug'
  126 |  debug(ans);
      |  ^~~~~
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
fences.cpp:128:2: note: in expansion of macro 'debug'
  128 |  debug(ans);
      |  ^~~~~
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
fences.cpp:130:2: note: in expansion of macro 'debug'
  130 |  debug(ans);
      |  ^~~~~
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
fences.cpp:132:2: note: in expansion of macro 'debug'
  132 |  debug(ans);
      |  ^~~~~
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
fences.cpp:134:2: note: in expansion of macro 'debug'
  134 |  debug(ans);
      |  ^~~~~
fences.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
fences.cpp:136:2: note: in expansion of macro 'debug'
  136 |  debug(ans);
      |  ^~~~~

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