Submission #132136

#	Time	Username	Problem	Language	Result	Execution time	Memory
132136		onjo0127	Fences (JOI18_fences)	C++11	51 / 100	1081 ms	155172 KiB

fences

#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pid = pair<int, double>;
using pdi = pair<double, int>;
using pdd = pair<double, double>;
#define X first
#define Y second
 
const double eps = 1e-6;
 
struct line { pdd S, E; };
struct dot { pdd D; int id; bool ps; };
struct node { double v; int c, id; };
 
bool operator <(node PP, node QQ) { return PP.v > QQ.v; }
 
inline double f(double x) { return max(x, -x); }
inline double dst(pdd A, pdd B) { return sqrt((A.X-B.X) * (A.X-B.X) + (A.Y-B.Y) * (A.Y-B.Y)); }
inline double CCW(pdd A, pdd B, pdd C) { return A.X*B.Y + B.X*C.Y + C.X*A.Y - A.Y*B.X - B.Y*C.X - C.Y*A.X; }
inline int CCWs(pdd A, pdd B, pdd C) {
	double tmp = CCW(A, B, C);
	if(f(tmp) < eps) return 0;
	if(tmp < 0) return -1;
	if(tmp > 0) return +1;
}
inline bool on(line A, pdd B) {
	if(A.S > A.E) swap(A.S, A.E);
	if(B < A.S || A.E < B) return false;
	return f(CCW(A.S, A.E, B)) < eps;
}
inline bool its(line A, line B) { // strict
	return CCWs(A.S, A.E, B.S) * CCWs(A.S, A.E, B.E) == -1 && CCWs(B.S, B.E, A.S) * CCWs(B.S, B.E, A.E) == -1;
}
inline pdd push(line A, pdd B) {
	double ds = dst(A.S, A.E);
	double d = f(CCW(A.S, A.E, B) / ds);
	double dx = A.S.Y - A.E.Y, dy = A.E.X - A.S.X;
	pdd PA = {B.X + dx * (d/ds), B.Y + dy * (d/ds)};
	pdd PB = {B.X - dx * (d/ds), B.Y - dy * (d/ds)};
	if(dst(PA, A.S) > dst(PB, A.S)) swap(PA, PB);
	return PA;
}
 
line I = {{0.0, 0.0}, {1000.0, 1.0}};
vector<dot> T;
vector<pid> adj[1000009];
line A[111];
int N, S, K;
double ans = 1e9, D[2][1000009];
bool IT[40009][40009];
 
inline bool ok(line L) {
	bool f = 0;
	f |= its(L, {{S, S}, {-S, -S}});
	f |= its(L, {{-S, S}, {S, -S}});
	return !f;
}
 
void dijk(int st) {
	// printf("start: (%d, %d)\n", T[st].D.X, T[st].D.Y);
	vector<pii> rec = {{0, st}};
	D[0][st] = 0.0;
	priority_queue<node> pq; pq.push({0.0, 0, st});
	while(pq.size()) {
		node n = pq.top(); pq.pop();
		if((n.id == st && n.c == 1) || n.v > ans) break;
		// printf("now: (%f, %d, (%d, %d))\n", n.v, n.c, T[n.id].D.X, T[n.id].D.Y);
		if(f(D[n.c][n.id] - n.v) > eps) continue;
		for(auto& it: adj[n.id]) {
			int tc = n.c;
			if(IT[n.id][it.X]) tc = 1 - tc;
			if(D[tc][it.X] > n.v + it.Y) {
				D[tc][it.X] = n.v + it.Y;
				rec.push_back({tc, it.X});
				pq.push({D[tc][it.X], tc, it.X});
			}
		}
	}
	ans = min(ans, D[1][st]);
	for(auto& it: rec) D[it.X][it.Y] = 1e9;
}
 
void make_edge(int u, int v, double c) {
	adj[u].push_back({v, c});
	adj[v].push_back({u, c});
}
 
int main() {
	scanf("%d%d",&N,&S);
	// N = 100; S = 100;
	ans = 8.0*S;
	for(int i=1; i<=N; i++) {
		scanf("%lf%lf%lf%lf", &A[i].S.X, &A[i].S.Y, &A[i].E.X, &A[i].E.Y);
		// A[i].S = {i, 100}; A[i].E = {i+1, 100};
		T.push_back({A[i].S, i, 0});
		T.push_back({A[i].E, i, 0});
	}
	T.push_back({{S, S}, N+1, 0});
	T.push_back({{S, -S}, N+2, 0});
	T.push_back({{-S, -S}, N+3, 0});
	T.push_back({{-S, S}, N+4, 0});
 
	int L = T.size();
 
	for(int i=1; i<=N; i++) {
		make_edge(2*i-2, 2*i-1, 0);
		for(int j=0; j<L; j++) {
			if(i == T[j].id) continue;
			pdd pu = push(A[i], T[j].D);
			double dp = dst(pu, T[j].D), ds = dst(T[j].D, A[i].S), de = dst(T[j].D, A[i].E);
			if(!ok({T[j].D, pu}) || !on(A[i], pu)) dp = 1e9;
			if(!ok({T[j].D, A[i].S})) ds = 1e9;
			if(!ok({T[j].D, A[i].E})) de = 1e9;
			if(min({ds, de, dp}) == 1e9) continue;
			if(dp <= ds && dp <= de) {
				int u = T.size();
				T.push_back({pu, i, 1});
				make_edge(u, j, dp);
				make_edge(u, 2*i-2, 0);
				continue;
			}
			if(ds <= de) make_edge(j, 2*i-2, ds);
			else make_edge(j, 2*i-1, de);
		}
	}
 
	for(int i=2*N; i<2*N+4; i++) {
		for(int j=i+1; j<2*N+4; j++) {
			if(!ok({T[i].D, T[j].D})) continue;
			make_edge(i, j, dst(T[i].D, T[j].D));
		}
	}
 
	K = T.size();
 
	for(int i=0; i<K; i++) {
		for(int j=i+1; j<K; j++) {
			if(its({T[i].D, T[j].D}, I)) IT[i][j] = IT[j][i] = 1;
		}
	}
 
	// printf("K: %d\n", K);
	// for(auto& it: T) {
	// 	printf("position(%f, %f), id: %d, pushed?: %d\n", it.D.X, it.D.Y, it.id, it.ps);
	// }
 
	for(int i=0; i<K; i++) D[0][i] = D[1][i] = 1e9;
	for(int i=0; i<2*N; i+=2) dijk(i);
	for(int i=2*N; i<2*N+4; i++) dijk(i);
	printf("%.10f", ans);
	return 0;
}

Compilation message (stderr)

fences.cpp: In function 'int main()':
fences.cpp:91: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:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lf%lf%lf%lf", &A[i].S.X, &A[i].S.Y, &A[i].E.X, &A[i].E.Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fences.cpp: In function 'int CCWs(pdd, pdd, pdd)':
fences.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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