oj.uz

답안 #132085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132085 2019-07-18T09:45:35 Z onjo0127 Fences (JOI18_fences) C++11
0 / 100
 28 ms 23928 KB 
#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; };
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];

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(its({T[it.X].D, T[n.id].D}, I)) 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);
	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);
		T.push_back({A[i].S, i});
		T.push_back({A[i].E, i});
	}
	T.push_back({{S, S}, N+1});
	T.push_back({{S, -S}, N+2});
	T.push_back({{-S, -S}, N+3});
	T.push_back({{-S, S}, N+4});

	for(int i=1; i<=N; i++) {
		make_edge(2*i-2, 2*i-1, 0);
		for(int j=0; j<T.size(); 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;
			double d = min({ds, de, dp});
			if(d == 1e9) continue;
			make_edge(j, 2*i-2, d);
		}
	}

	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();

	// 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

fences.cpp: In function 'int main()':
fences.cpp:103:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<T.size(); j++) {
                ~^~~~~~~~~
fences.cpp: In function 'int CCWs(pdd, pdd, pdd)':
fences.cpp:26:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
fences.cpp: In function 'int main()':
fences.cpp:89: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:92: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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 23 ms 23800 KB Output is correct
5 Correct 23 ms 23800 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 23 ms 23804 KB Output is correct
8 Correct 23 ms 23800 KB Output is correct
9 Correct 23 ms 23800 KB Output is correct
10 Correct 23 ms 23800 KB Output is correct
11 Correct 25 ms 23800 KB Output is correct
12 Correct 23 ms 23800 KB Output is correct
13 Incorrect 28 ms 23928 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 23 ms 23800 KB Output is correct
5 Correct 23 ms 23800 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 23 ms 23804 KB Output is correct
8 Correct 23 ms 23800 KB Output is correct
9 Correct 23 ms 23800 KB Output is correct
10 Correct 23 ms 23800 KB Output is correct
11 Correct 25 ms 23800 KB Output is correct
12 Correct 23 ms 23800 KB Output is correct
13 Incorrect 28 ms 23928 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 23 ms 23800 KB Output is correct
5 Correct 23 ms 23800 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 23 ms 23804 KB Output is correct
8 Correct 23 ms 23800 KB Output is correct
9 Correct 23 ms 23800 KB Output is correct
10 Correct 23 ms 23800 KB Output is correct
11 Correct 25 ms 23800 KB Output is correct
12 Correct 23 ms 23800 KB Output is correct
13 Incorrect 28 ms 23928 KB Output isn't correct
14 Halted 0 ms 0 KB -