| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 131957 |
2019-07-18T06:34:08 Z |
이온조(#3189) |
Fences (JOI18_fences) |
C++14 |
|
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
