Submission #57064

#	Time	Username	Problem	Language	Result	Execution time	Memory
57064		cki86201	Fences (JOI18_fences)	C++11	100 / 100	225 ms	3824 KiB

fences

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()
typedef tuple<int, int, int> t3;

struct point {
	double x, y;
	point(){}
	point(double x, double y) : x(x), y(y) {}
	point operator-(point a) { return point(x - a.x, y - a.y); }
	point operator+(point a) { return point(x + a.x, y + a.y); }
	double operator*(point a) { return x * a.x + y * a.y; }
	point operator*(double a) { return point(x * a, y * a); }
	double operator/(point a) { return x * a.y - y * a.x; }
	double length() { return hypot(x, y); }
};

vector <point> V;
int N, S;
point In[110][2];
const double EPS = 1e-9;

inline int p1_in(double x) { return -S + EPS < x && x < S - EPS; }
inline int seg1_in(double l1, double r1, double l2, double r2) {
	if(l1 > r1) swap(l1, r1);
	if(l2 > r2) swap(l2, r2);
	return max(l1, l2) + EPS < min(r1, r2);
}

int is_in(point a, point b) {
	if(fabs(a.x - b.x) <= EPS) { swap(a.x, a.y); swap(b.x, b.y); }
	if(fabs(a.x - b.x) <= EPS) {
		return p1_in(a.x) && p1_in(a.y);
	}
	if(fabs(a.y - b.y) <= EPS) {
		if(p1_in(a.y) && seg1_in(a.x, b.x, -S, S)) return 1;
		return 0;
	}
	double lx = (-S - a.x) / (b.x - a.x);
	double rx = (S - a.x) / (b.x - a.x);
	if(lx > rx) swap(lx, rx);
	double ly = (-S - a.y) / (b.y - a.y);
	double ry = (S - a.y) / (b.y - a.y);
	if(ly > ry) swap(ly, ry);
	double L = max({lx, ly, 0.0});
	double R = min({rx, ry, 1.0});
	if(L + EPS < R) return 1;
	return 0;
}

typedef pair<double, int> pdi;

vector <point> PS;
vector <pdi> E[50050];

int sign(double x) {
	if(fabs(x) <= EPS) return 0;
	return x > 0 ? 1 : -1;
}

int seg2_in(point a, point b, point c, point d) {
	return sign((b-a) / (c-a)) * sign((b-a) / (d-a)) == -1 && sign((d-c) / (a-c)) * sign((d-c) / (b-c)) == -1;
}

int meet(int a, int b) {
	point p1 = point(0, 0);
	point p2 = point(400 + sqrt(2), 1);
	return seg2_in(PS[a], PS[b], p1, p2);
}

void add_edge(int a, int b, double len = -1) {
	if(is_in(PS[a], PS[b])) return;
	int c = meet(a, b);
	if(len == -1) len = (PS[a] - PS[b]).length();
	rep(u, 2) {
		E[a<<1^u].pb(pdi(len, b<<1^u^c));
		E[b<<1^u^c].pb(pdi(len, a<<1^u));
	}
}

double dis[50050];
double get_min(int x) {
	int s = x * 2, des = s + 1;
	priority_queue <pdi, vector<pdi>, greater<pdi> > pq;
	int N = szz(PS) * 2;
	rep(i, N) dis[i] = 1e9;
	dis[s] = 0; pq.push(pdi(0, s));
	while(!pq.empty()) {
		pdi t = pq.top(); pq.pop();
		if(dis[t.Se] != t.Fi) continue;
		if(t.Se == des) return t.Fi;
		for(pdi e : E[t.Se]) {
			if(e.Fi + t.Fi < dis[e.Se]) {
				dis[e.Se] = e.Fi + t.Fi;
				pq.push(pdi(dis[e.Se], e.Se));
			}
		}
	}
	return dis[des];
}

void solve(){
	scanf("%d%d", &N, &S);
	for(int x : {-S, S}) for(int y : {-S, S}) PS.pb(point(x, y));
	rep(i, N) {
		int l = szz(PS);
		rep(j, 2) {
			int x, y; scanf("%d%d", &x, &y);
			In[i][j] = point(x, y);
			PS.pb(In[i][j]);
		}
		add_edge(l, l+1, 0);
	}
	rep(i, szz(PS)) rep(j, i) add_edge(i, j);
	rep(i, 2*N+4) rep(j, N) {
		point a = In[j][0], b = In[j][1];
		point p = PS[i];
		if((p-a) * (b-a) > EPS && (p-b) * (a-b) > EPS) {
			double v = ((p-a) * (b-a)) / ((b-a) * (b-a));
			point h = a + (b-a) * v;
			int ok = 1;
			rep(k, N) if(seg2_in(p, h, In[k][0], In[k][1])) { ok = 0; break; }
		//	printf("p = (%.1f, %.1f), a = (%.1f, %.1f), b = (%.1f, %.1f), h = (%.1f, %.1f)\n", p.x, p.y, a.x, a.y, b.x, b.y, h.x, h.y);
			if(ok) {
				int z = szz(PS);
				PS.pb(h);
				add_edge(2 * j + 4, z, 0);
				add_edge(2 * j + 5, z, 0);
				add_edge(z, i);
			}
		}
	}
	
	double ans = 1e9;
	rep(i, 2*N+4) ans = min(ans, get_min(i));
	printf("%.12f\n", ans);
}

int main(){
	int Tc = 1; //scanf("%d", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}

Compilation message (stderr)

fences.cpp: In function 'void solve()':
fences.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &S);
  ~~~~~^~~~~~~~~~~~~~~~
fences.cpp:129:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x, y; scanf("%d%d", &x, &y);
              ~~~~~^~~~~~~~~~~~~~~~

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