| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 173456 |
2020-01-04T07:38:37 Z |
super_j6 |
Fences (JOI18_fences) |
C++14 |
|
74 ms |
1784 KB |
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <math.h>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
int cp(long long x, long long y, int X, int Y){
return x * Y == X * y ? 0 : x * Y < X * y ? -1 : 1;
}
int il(int x1, int y1, int X1, int Y1, int x2, int y2, int X2, int Y2){
int a = cp(X1 - x1, Y1 - y1, x2 - x1, y2 - y1);
int b = cp(X1 - x1, Y1 - y1, X2 - x1, Y2 - y1);
int c = cp(X2 - x2, Y2 - y2, x1 - x2, y1 - y2);
int d = cp(X2 - x2, Y2 - y2, X1 - x2, Y1 - y2);
return a && b && c && d && a != b && c != d;
}
const int maxn = 408, p = 1000000007;
int n, s, m;
int a[maxn], b[maxn];
double dp[maxn][maxn];
int gc(int x, int y, int X, int Y){
return il(x, y, X, Y, 0, 0, p, 1) ? cp(x, y, p, 1) : 0;
}
void up(int i, int j, double d, int c){
c &= 1;
dp[i][j + c * m] = min(dp[i][j + c * m], d);
dp[j + c * m][i] = min(dp[j + c * m][i], d);
dp[i + m][j + (1 - c) * m] = min(dp[i + m][j + (1 - c) * m], d);
dp[j + (1 - c) * m][i + m] = min(dp[j + (1 - c) * m][i + m], d);
}
void di(long long x, long long y, int X, int Y, int s, double &d){
for(int i = 2 * n; i < 2 * n + 2; i++){
if(il(x, y, X, Y, a[i] * s, b[i] * s, a[i + 2] * s, b[i + 2] * s)){
return;
}
}
d = sqrt((X - x) * (X - x) + (Y - y) * (Y - y)) / s;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout << fixed << setprecision(6);
cin >> n >> s;
m = 2 * n + 4;
for(int i = 0; i < n; i++){
cin >> a[2 * i] >> b[2 * i] >> a[2 * i + 1] >> b[2 * i + 1];
}
a[2 * n] = a[2 * n + 1] = b[2 * n] = b[2 * n + 3] = s;
a[2 * n + 2] = a[2 * n + 3] = b[2 * n + 1] = b[2 * n + 2] = -s;
for(int i = 0; i < 2 * m; i++)
for(int j = 0; j < 2 * m; j++){
dp[i][j] = 8 * s;
}
/*
for(int i = 0; i < n; i++)
for(int j = 0; j < i; j++){
if(il(a[2 * i], b[2 * i], a[2 * i + 1], b[2 * i + 1], a[2 * j], b[2 * j], a[2 * j + 1], b[2 * j + 1])){
for(int k = 0; k < 4; k++){
up(2 * i + k % 2, 2 * j + k / 2, 0, gc(a[2 * i + k % 2], b[2 * i + k % 2], a[2 * j + k / 2], b[2 * j + k / 2]));
}
}
}
*/
for(int i = 0; i < m; i++)
for(int j = 0; 2 * j < m; j++){
double d = 8 * s;
for(int k = 2 * j; k < 2 * j + 2; k++, d = 8 * s){
di(a[i], b[i], a[k], b[k], 1, d);
if(d < 8 * s){
up(i, k, d, gc(a[i], b[i], a[k], b[k]));
}
}
if(j < n){
int bx = a[2 * j + 1] - a[2 * j], by = b[2 * j + 1] - b[2 * j];
int bm = bx * bx + by * by, adb = (a[i] - a[2 * j]) * bx + (b[i] - b[2 * j]) * by;
if(0 <= adb && adb <= bm){
int cx = adb * bx + a[2 * j] * bm, cy = adb * by + b[2 * j] * bm;
di(a[i] * bm, b[i] * bm, cx, cy, bm, d);
if(d < 8 * s){
for(int k = 2 * j; k < 2 * j + 2; k++){
up(i, k, d, gc(a[i] * bm, b[i] * bm, cx, cy) + gc(cx, cy, a[k] * bm, b[k] * bm));
}
}
}
}
}
for(int k = 0; k < 2 * m; k++)
for(int i = 0; i < 2 * m; i++)
for(int j = 0; j < 2 * m; j++){
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
}
double ret = 8 * s;
for(int i = 0; i < m; i++){
ret = min(ret, dp[i][i + m]);
}
cout << ret << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
380 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
380 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| 22 |
Correct |
2 ms |
376 KB |
Output is correct |
| 23 |
Correct |
3 ms |
376 KB |
Output is correct |
| 24 |
Correct |
3 ms |
504 KB |
Output is correct |
| 25 |
Correct |
3 ms |
376 KB |
Output is correct |
| 26 |
Correct |
2 ms |
504 KB |
Output is correct |
| 27 |
Correct |
3 ms |
504 KB |
Output is correct |
| 28 |
Correct |
3 ms |
376 KB |
Output is correct |
| 29 |
Correct |
2 ms |
376 KB |
Output is correct |
| 30 |
Correct |
2 ms |
504 KB |
Output is correct |
| 31 |
Correct |
2 ms |
376 KB |
Output is correct |
| 32 |
Correct |
2 ms |
376 KB |
Output is correct |
| 33 |
Correct |
3 ms |
376 KB |
Output is correct |
| 34 |
Correct |
3 ms |
380 KB |
Output is correct |
| 35 |
Correct |
2 ms |
376 KB |
Output is correct |
| 36 |
Correct |
3 ms |
504 KB |
Output is correct |
| 37 |
Correct |
3 ms |
508 KB |
Output is correct |
| 38 |
Correct |
2 ms |
376 KB |
Output is correct |
| 39 |
Correct |
3 ms |
376 KB |
Output is correct |
| 40 |
Correct |
2 ms |
376 KB |
Output is correct |
| 41 |
Correct |
3 ms |
376 KB |
Output is correct |
| 42 |
Correct |
3 ms |
428 KB |
Output is correct |
| 43 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
380 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| 22 |
Correct |
2 ms |
376 KB |
Output is correct |
| 23 |
Correct |
3 ms |
376 KB |
Output is correct |
| 24 |
Correct |
3 ms |
504 KB |
Output is correct |
| 25 |
Correct |
3 ms |
376 KB |
Output is correct |
| 26 |
Correct |
2 ms |
504 KB |
Output is correct |
| 27 |
Correct |
3 ms |
504 KB |
Output is correct |
| 28 |
Correct |
3 ms |
376 KB |
Output is correct |
| 29 |
Correct |
2 ms |
376 KB |
Output is correct |
| 30 |
Correct |
2 ms |
504 KB |
Output is correct |
| 31 |
Correct |
2 ms |
376 KB |
Output is correct |
| 32 |
Correct |
2 ms |
376 KB |
Output is correct |
| 33 |
Correct |
3 ms |
376 KB |
Output is correct |
| 34 |
Correct |
3 ms |
380 KB |
Output is correct |
| 35 |
Correct |
2 ms |
376 KB |
Output is correct |
| 36 |
Correct |
3 ms |
504 KB |
Output is correct |
| 37 |
Correct |
3 ms |
508 KB |
Output is correct |
| 38 |
Correct |
2 ms |
376 KB |
Output is correct |
| 39 |
Correct |
3 ms |
376 KB |
Output is correct |
| 40 |
Correct |
2 ms |
376 KB |
Output is correct |
| 41 |
Correct |
3 ms |
376 KB |
Output is correct |
| 42 |
Correct |
3 ms |
428 KB |
Output is correct |
| 43 |
Correct |
2 ms |
376 KB |
Output is correct |
| 44 |
Correct |
73 ms |
1724 KB |
Output is correct |
| 45 |
Correct |
74 ms |
1692 KB |
Output is correct |
| 46 |
Correct |
73 ms |
1656 KB |
Output is correct |
| 47 |
Correct |
72 ms |
1656 KB |
Output is correct |
| 48 |
Correct |
74 ms |
1656 KB |
Output is correct |
| 49 |
Correct |
73 ms |
1684 KB |
Output is correct |
| 50 |
Correct |
73 ms |
1656 KB |
Output is correct |
| 51 |
Correct |
72 ms |
1784 KB |
Output is correct |
| 52 |
Correct |
72 ms |
1684 KB |
Output is correct |
| 53 |
Correct |
72 ms |
1688 KB |
Output is correct |
| 54 |
Correct |
72 ms |
1688 KB |
Output is correct |
| 55 |
Correct |
73 ms |
1656 KB |
Output is correct |
| 56 |
Correct |
73 ms |
1784 KB |
Output is correct |
| 57 |
Correct |
73 ms |
1656 KB |
Output is correct |
| 58 |
Correct |
72 ms |
1656 KB |
Output is correct |
| 59 |
Correct |
73 ms |
1724 KB |
Output is correct |
| 60 |
Correct |
72 ms |
1656 KB |
Output is correct |
| 61 |
Correct |
73 ms |
1656 KB |
Output is correct |
| 62 |
Correct |
2 ms |
504 KB |
Output is correct |
| 63 |
Correct |
2 ms |
552 KB |
Output is correct |
| 64 |
Correct |
67 ms |
1656 KB |
Output is correct |
| 65 |
Correct |
71 ms |
1660 KB |
Output is correct |
| 66 |
Correct |
66 ms |
1656 KB |
Output is correct |
| 67 |
Correct |
65 ms |
1656 KB |
Output is correct |
| 68 |
Correct |
66 ms |
1528 KB |
Output is correct |
| 69 |
Correct |
73 ms |
1684 KB |
Output is correct |
| 70 |
Correct |
61 ms |
1528 KB |
Output is correct |
| 71 |
Correct |
71 ms |
1784 KB |
Output is correct |
| 72 |
Correct |
72 ms |
1784 KB |
Output is correct |
