Submission #47925

#	Time	Username	Problem	Language	Result	Execution time	Memory
47925		Kmcode	Fences (JOI18_fences)	C++14	0 / 100	2 ms	376 KiB

fences

#include "bits/stdc++.h"
using namespace std;

#define MAX 102

const double EPS = 1e-12;

int n;
int s;

struct seg {
	complex<double> p1;
	complex<double> p2;
	seg() {

	}
	seg(int a, int b, int c, int d) {
		p1 = complex<double>(a, b);
		p2 = complex<double>(c, d);
	}
	seg(complex<double> p11, complex<double> p21) {
		p1 = p11;
		p2 = p21;
	}
};

vector<seg> v;


double cross(complex<double> a, complex<double> b) {
	return a.real()*b.imag() - a.imag()*b.real();
}
int sig(double val) {
	if (abs(val) < EPS) {
		return 0;
	}
	if (val < 0.0) {
		return -1;
	}
	return 1;
}
bool isparallel(seg a, seg b) {
	auto vec1 = a.p1 - a.p2;
	auto vec2 = b.p1 - b.p2;
	return abs(cross(vec1, vec2)) < EPS;
}
bool online(complex<double> a, seg b) {
	return abs(abs(a - b.p1) + abs(a - b.p2) - abs(b.p1 - b.p2)) < EPS;
}
bool isintersect(seg a, seg b) {
	if (online(a.p1, b) || online(a.p2, b) || online(b.p1, a) || online(b.p2, a))return true;
	if (sig(cross(a.p1 - a.p2, b.p1 - a.p2)) == sig(cross(a.p1 - a.p2, b.p2 - a.p2)))return false;
	if (sig(cross(a.p2 - a.p1, b.p1 - a.p1)) == sig(cross(a.p2 - a.p1, b.p2 - a.p1)))return false;
	if (sig(cross(b.p1 - b.p2, a.p1 - b.p2)) == sig(cross(b.p1 - b.p2, a.p2 - b.p2)))return false;
	if (sig(cross(b.p2 - b.p1, a.p1 - b.p1)) == sig(cross(b.p2 - b.p1, a.p2 - b.p1)))return false;
	return true;
}
complex<double> intersect(seg a, seg b) {  //be assured of checking isintersect first
	double A = cross(a.p2 - a.p1, a.p1 - b.p1);
	double B = cross(a.p2 - a.p1, b.p2 - b.p1);
	return b.p1 + (b.p2 - b.p1)*A / B;
}


complex<double> project(complex<double> a, seg b) {
	auto base = b.p1;
	b.p2 -= b.p1;
	a -= b.p1;
	auto cr = cross(b.p2, a) / abs(b.p2);
	double ds = sqrt(abs(a)*abs(a) - cr*cr + EPS);
	return base + b.p2*ds / abs(b.p2);
}
long long int dt(complex<double> a, complex<double> b) {
	return a.real()*b.real() + a.imag()*b.imag();
}
pair<double, complex<double> > dist(complex<double> p, seg a) {
	if (online(p, a))return make_pair(0, p);
	auto mi = make_pair(abs(p - a.p1), a.p1);
	if (mi.first > abs(p - a.p2)) {
		mi = make_pair(abs(p - a.p2), a.p2);
	}
	int A = sig(dt(a.p1 - a.p2, p - a.p2));
	int B = sig(dt(a.p2 - a.p1, p - a.p1));
	if (A == -1 || B == -1) {
		return mi;
	}
	auto tmp = a;
	auto pp = p;
	p -= a.p1;
	a.p2 -= a.p1;
	return make_pair(abs(cross(a.p2, p) / abs(a.p2)), project(pp, tmp));
}
pair<complex<double>, complex<double> > dist(seg a, seg b) {
	if (isintersect(a, b)) {
		return make_pair(intersect(a, b), intersect(a, b));
	}
	auto a1 = dist(a.p1, b);
	auto a2 = dist(a.p2, b);
	auto a3 = dist(b.p1, a);
	auto a4 = dist(b.p2, a);
	double A = min(a1.first, min(a2.first, min(a3.first, a4.first)));
	if (a1.first == A)return make_pair(a.p1, a1.second);
	if (a2.first == A)return make_pair(a.p2, a2.second);
	if (a3.first == A)return make_pair(a3.second, b.p1);
	if (a4.first == A)return make_pair(a4.second, b.p2);
}
int l;

seg magic;

double dp[210 * 2][210 * 2];


pair<bool, double> MOV(seg a, seg b) {
	auto it = dist(a, b);
	bool fl = false;
	fl ^= isintersect(seg(a.p1, it.first), magic);
	fl ^= isintersect(seg(it.first, it.second), magic);
	fl ^= isintersect(seg(it.second, b.p1), magic);
	return make_pair(fl, abs(it.first - it.second));
}
pair<bool, double> MOV_en(seg a, seg b) {
	auto it = dist(a, b);
	bool fl = false;
	fl ^= isintersect(seg(a.p1, it.first), magic);
	fl ^= isintersect(seg(it.first, it.second), magic);
	return make_pair(fl, abs(it.first - it.second));
}
//四角形の交差判定を追加しないといけない
int main() {
	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		v.push_back(seg(a, b, c, d));
	}
	v.push_back(seg(-s, s, s, s));
	v.push_back(seg(-s, -s, s, -s));
	v.push_back(seg(-s, -s, -s, s));
	v.push_back(seg(s, -s, s, s));
	magic = seg(0, 0, 141253, 1000000007);
	for (int i = 0; i < v.size() * 2; i++) {
		for (int j = 0; j < v.size() * 2; j++) {
			dp[i][j] = INT_MAX;
		}
		dp[i][i] = 0;
		int cur = i / 2;
		for (int j = 0; j < v.size(); j++) {
			if (cur == j)continue;
			auto f = MOV(v[cur], v[j]);
			dp[i][j * 2 + f.first] = f.second;
		}
	}
	for (int k = 0; k < v.size() * 2; k++) {
		for (int i = 0; i < v.size() * 2; i++) {
			for (int j = 0; j < v.size() * 2; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
	double ans = INT_MAX;
	for (int i = 0; i < v.size() * 2; i++) {
		if (i & 1)continue;
		for (int j = 0; j < v.size() * 2; j++) {
			if (i / 2 == j / 2)continue;
			bool stat = (j & 1);
			auto f = MOV_en(v[j / 2], v[i / 2]);
			double cost = dp[i][j] + f.second;
			stat ^= f.first;
			if (stat) {
				ans = min(ans, cost);
			}
		}
	}
	printf("%.16f\n", ans);
	return 0;
}

Compilation message (stderr)

fences.cpp: In function 'int main()':
fences.cpp:142:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size() * 2; i++) {
                  ~~^~~~~~~~~~~~~~
fences.cpp:143:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < v.size() * 2; j++) {
                   ~~^~~~~~~~~~~~~~
fences.cpp:148:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < v.size(); j++) {
                   ~~^~~~~~~~~~
fences.cpp:154:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int k = 0; k < v.size() * 2; k++) {
                  ~~^~~~~~~~~~~~~~
fences.cpp:155:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < v.size() * 2; i++) {
                   ~~^~~~~~~~~~~~~~
fences.cpp:156:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < v.size() * 2; j++) {
                    ~~^~~~~~~~~~~~~~
fences.cpp:162:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size() * 2; i++) {
                  ~~^~~~~~~~~~~~~~
fences.cpp:164:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < v.size() * 2; j++) {
                   ~~^~~~~~~~~~~~~~
fences.cpp: In function 'std::pair<std::complex<double>, std::complex<double> > dist(seg, seg)':
fences.cpp:106:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
fences.cpp: In function 'int main()':
fences.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &a, &b, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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