| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 47809 |
2018-05-07T13:37:38 Z |
Kmcode |
Fences (JOI18_fences) |
C++14 |
|
2 ms |
376 KB |
#include "bits/stdc++.h"
using namespace std;
#define MAX 102
const double EPS = 1e-12;
int n;
int s;
struct seg {
complex<double> p1;
complex<double> p2;
seg() {
}
seg(int a, int b, int c, int d) {
p1 = complex<double>(a, b);
p2 = complex<double>(c,d);
}
seg(complex<double> p11, complex<double> p21) {
p1 = p11;
p2 = p21;
}
};
vector<seg> v;
double cross(complex<double> a, complex<double> b) {
return a.real()*b.imag() - a.imag()*b.real();
}
int sig(double val) {
if (abs(val) < EPS) {
return 0;
}
if (val < 0.0) {
return -1;
}
return 1;
}
bool isparallel(seg a, seg b) {
auto vec1 = a.p1 - a.p2;
auto vec2 = b.p1 - b.p2;
return abs(cross(vec1, vec2) ) < EPS;
}
bool online(complex<double> a, seg b) {
return abs(abs(a - b.p1) + abs(a - b.p2) - abs(b.p1 - b.p2)) < EPS;
}
bool isintersect(seg a, seg b) {
if (isparallel(a, b)) {
if (a.p1.real() > a.p2.real()) {
swap(a.p1, a.p2);
}
if (b.p1.real() > b.p2.real()) {
swap(b.p1, b.p2);
}
if (a.p2.real() + EPS < b.p1.real()) {
return false;
}
return true;
}
if (online(a.p1, b) || online(a.p2, b) || online(b.p1, a) || online(b.p2, a))return true;
if (sig(cross(a.p1, b.p1)) == sig(cross(a.p1, b.p2)))return false;
if (sig(cross(a.p2, b.p1))== sig(cross(a.p2, b.p2)))return false;
if (sig(cross(b.p1, a.p1)) == sig(cross(b.p1, a.p2)))return false;
if (sig(cross(b.p2, a.p1)) == sig(cross(b.p2, a.p2)))return false;
return true;
}
complex<double> intersect(seg a, seg b) { //be assured of checking isintersect first
double A = cross(a.p2 - a.p1,a.p1 - b.p1);
double B = cross(a.p2 - a.p1,b.p2 - b.p1);
return b.p1 + (b.p2 - b.p1)*A / B;
}
complex<double> project(complex<double> a,seg b) {
auto base = b.p1;
b.p2 -= b.p1;
a -= b.p1;
auto cr = cross(b.p2, a)/abs(b.p2);
double ds = sqrt(abs(a)*abs(a) - cr*cr+EPS);
return base + b.p2*ds / abs(b.p2);
}
pair<double,complex<double> > dist(complex<double> p, seg a) {
if (online(p, a))return make_pair(0, p);
auto mi = make_pair(abs(p - a.p1), a.p1);
if (mi.first > abs(p - a.p2)) {
mi = make_pair(abs(p - a.p2), a.p2);
}
int A = sig(cross(a.p1, p));
int B = sig(cross(a.p2, p));
if (A == B&&A != 0) {
return mi;
}
p -= a.p1;
a.p2 -= a.p1;
return make_pair(cross(a.p2, p) / abs(a.p2), project(p, a));
}
pair<complex<double>,complex<double> > dist(seg a, seg b) {
if (isintersect(a, b)) {
return make_pair(intersect(a, b), intersect(a, b));
}
auto a1 = dist(a.p1, b);
auto a2 = dist(a.p2, b);
auto a3 = dist(b.p1, a);
auto a4 = dist(b.p2, b);
double A = min(a1.first, min(a2.first, min(a3.first, a4.first)));
if (a1.first == A)return make_pair(a.p1,a1.second);
if (a2.first == A)return make_pair(a.p2,a2.second);
if (a3.first == A)return make_pair(a3.second,b.p1);
if (a4.first == A)return make_pair(a4.second,b.p2);
}
int l;
seg magic;
double dp[210 * 2][210 * 2];
pair<bool, double> MOV(seg a, seg b) {
auto it = dist(a, b);
bool fl = false;
fl^=isintersect(seg(a.p1, it.first), magic);
fl ^= isintersect(seg(it.first, it.second), magic);
fl ^= isintersect(seg(it.second, b.p1), magic);
return make_pair(fl, abs(it.first - it.second));
}
int main() {
cin >> n >> s;
for (int i = 0; i < n; i++) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
v.push_back(seg(a,b,c,d));
}
v.push_back(seg(-s, s, s, s));
v.push_back(seg(-s, -s, s, -s));
v.push_back(seg(-s, -s, -s, s));
v.push_back(seg(s, -s, s, s));
magic = seg(0, 0, 141253, 1000000007);
for (int i = 0; i < v.size()*2; i++) {
for (int j = 0; j < v.size()*2; j++) {
dp[i][j] = INT_MAX;
}
dp[i][i] = 0;
int cur = i / 2;
for (int j = 0; j < v.size(); j++) {
if (cur == j)continue;
auto f = MOV(v[cur], v[j]);
dp[i][j * 2 + f.first] = f.second;
}
}
for (int k = 0; k < v.size() * 2; k++) {
for (int i = 0; i < v.size() * 2; i++) {
for (int j = 0; j < v.size() * 2; j++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
double ans = INT_MAX;
for (int i = 0; i < v.size() * 2; i++) {
if (i & 1)continue;
for (int j = 0; j < v.size() * 2; j++) {
bool stat = (j & 1);
auto f = MOV(v[j / 2], v[i / 2]);
double cost = dp[i][j] + f.second;
stat ^= f.first;
if (stat) {
ans = min(ans, cost);
}
}
}
printf("%.16f\n",ans);
return 0;
}
Compilation message
fences.cpp: In function 'int main()':
fences.cpp:142:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size()*2; i++) {
~~^~~~~~~~~~~~
fences.cpp:143:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size()*2; j++) {
~~^~~~~~~~~~~~
fences.cpp:148:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size(); j++) {
~~^~~~~~~~~~
fences.cpp:154:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < v.size() * 2; k++) {
~~^~~~~~~~~~~~~~
fences.cpp:155:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size() * 2; i++) {
~~^~~~~~~~~~~~~~
fences.cpp:156:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size() * 2; j++) {
~~^~~~~~~~~~~~~~
fences.cpp:162:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size() * 2; i++) {
~~^~~~~~~~~~~~~~
fences.cpp:164:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size() * 2; j++) {
~~^~~~~~~~~~~~~~
fences.cpp: In function 'std::pair<std::complex<double>, std::complex<double> > dist(seg, seg)':
fences.cpp:113:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
fences.cpp: In function 'int main()':
fences.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &a, &b, &c, &d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
