oj.uz

답안 #131957

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
131957 2019-07-18T06:34:08 Z 이온조(#3189) Fences (JOI18_fences) C++14
0 / 100
 9 ms 2724 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pdi = pair<double, int>;
#define X first
#define Y second

const double eps = 1e-6;

struct line { pii S, E; };
struct dot { pii 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 int CCW(pii A, pii B, pii 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(pii A, pii B, pii C) {
	int tmp = CCW(A, B, C);
	if(tmp < 0) return -1;
	if(tmp > 0) return +1;
	if(tmp == 0) return 0;
}
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;
}

line I = {{0, 0}, {1000, 1}};
vector<dot> T;
vector<pii> adj[100009];
line A[111];
int N, S, K;

double ans = 1e9, D[2][100009];

bool chk[111];

inline bool ok(line L) {
	bool f = 0;
	f |= its(L, {{S, S}, {S, -S}});
	f |= its(L, {{S, -S}, {-S, -S}});
	f |= its(L, {{-S, -S}, {-S, S}});
	f |= its(L, {{-S, S}, {S, S}});
	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);

	for(int i=0; i<K; i++) D[0][i] = D[1][i] = 1e9;
	D[0][st] = 0.0;
	priority_queue<node> pq; pq.push({0.0, 0, st});
	while(pq.size()) {
		node n = pq.top(); pq.pop();
		// 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;
		if(n.id == st && n.c == 1) break;
		for(auto& it: adj[n.id]) {
			int tc = n.c;
			if(its({T[n.id].D, T[it.X].D}, I)) tc = 1 - tc;
			if(D[tc][it.X] > n.v + sqrt(it.Y)) {
				D[tc][it.X] = n.v + sqrt(it.Y);
				pq.push({D[tc][it.X], tc, it.X});
			}
		}
	}
	ans = min(ans, D[1][st]);
}

int main() {
	scanf("%d%d",&N,&S);
	assert(N == 1);
	for(int i=1; i<=N; i++) {
		scanf("%d%d%d%d", &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});

	K = T.size();
	for(int i=0; i<K; i++) {
		for(int j=i+1; j<K; j++) {
			if(!ok({T[i].D, T[j].D})) continue;
			double d;
			if(T[i].id == T[j].id) d = 0;
			else d = (T[i].D.X - T[j].D.X) * (T[i].D.X - T[j].D.X) + (T[i].D.Y - T[j].D.Y) * (T[i].D.Y - T[j].D.Y);

			// printf("(%d, %d) <----> (%d, %d), cost: %f\n", T[i].D.X, T[i].D.Y, T[j].D.X, T[j].D.Y, d);
			adj[i].push_back({j, d});
			adj[j].push_back({i, d});
		}
	}

	for(int i=0; i<K; i++) if(!chk[T[i].id]) {
		dijk(i);
		chk[T[i].id] = 1;
	}
	printf("%.10f", ans);
	return 0;
}

Compilation message

fences.cpp: In function 'int CCWs(pii, pii, pii)':
fences.cpp:23:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
fences.cpp: In function 'int main()':
fences.cpp:73: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:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &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 5 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 4 ms 2684 KB Output is correct
5 Correct 5 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Incorrect 9 ms 2724 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 4 ms 2684 KB Output is correct
5 Correct 5 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Incorrect 9 ms 2724 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 4 ms 2684 KB Output is correct
5 Correct 5 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Incorrect 9 ms 2724 KB Output isn't correct
8 Halted 0 ms 0 KB -