# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
47521 |
2018-05-04T15:34:38 Z |
qoo2p5 |
Fences (JOI18_fences) |
C++17 |
|
2 ms |
536 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;
#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
bool mini(auto &x, const auto &y) {
if (y < x) {
x = y;
return 1;
}
return 0;
}
bool maxi(auto &x, const auto &y) {
if (y > x) {
x = y;
return 1;
}
return 0;
}
void run();
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
run();
return 0;
}
typedef long double ld;
struct Vect {
ll x, y;
Vect() : x(0), y(0) {}
Vect(ll x, ll y) : x(x), y(y) {}
Vect(const Vect &a, const Vect &b) : x(b.x - a.x), y(b.y - a.y) {}
Vect operator+(const Vect &b) const {
return Vect(x + b.x, y + b.y);
}
bool operator==(const Vect &b) const {
return mp(x, y) == mp(b.x, b.y);
}
ld len() const {
return hypot(x, y);
}
ll operator*(const Vect &b) {
return x * b.y - b.x * y;
}
ll len2() const {
return x * x + y * y;
}
};
const int N = 101;
int n;
Vect a[N], b[N];
ll s;
vector<Vect> convex(vector<Vect> p) {
Vect start = *min_element(all(p), [] (auto &x, auto &y) {
return mp(x.x, x.y) < mp(y.x, y.y);
});
sort(all(p), [&] (auto &x, auto &y) {
Vect u = Vect(start, x);
Vect v = Vect(start, y);
if (u * v > 0) {
return true;
}
if (u * v < 0) {
return false;
}
return u.len2() < v.len2();
});
vector<Vect> st;
for (auto &v : p) {
while (sz(st) >= 2 && Vect(st[sz(st) - 2], st[sz(st) - 1]) * Vect(st[sz(st) - 1], v) <= 0) {
st.pop_back();
}
st.pb(v);
}
return st;
}
bool test(int mask, int bit) {
return mask & (1 << bit);
}
void run() {
cin >> n >> s;
rep(i, 0, n) {
cin >> a[i].x >> a[i].y >> b[i].x >> b[i].y;
}
ld ans = 8 * s;
vector<Vect> p = {{s, s}, {s, -s}, {-s, -s}, {-s, s}};
rep(mask, 0, 1 << n) {
ld cur = 0;
vector<Vect> tmp = p;
rep(i, 0, n) {
if (test(mask, i)) {
tmp.pb(a[i]);
tmp.pb(b[i]);
}
}
tmp = convex(tmp);
tmp.pb(tmp[0]);
rep(i, 0, sz(tmp) - 1) {
Vect x = tmp[i];
Vect y = tmp[i + 1];
ld cost = Vect(x, y).len();
rep(j, 0, n) {
if (!test(mask, j)) {
continue;
}
if (mp(x, y) == mp(a[j], b[j]) || mp(x, y) == mp(b[j], a[j])) {
cost = 0;
}
}
cur += cost;
}
mini(ans, cur);
}
cout << fixed << setprecision(10) << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
360 KB |
Output is correct |
3 |
Correct |
2 ms |
472 KB |
Output is correct |
4 |
Correct |
2 ms |
492 KB |
Output is correct |
5 |
Correct |
2 ms |
496 KB |
Output is correct |
6 |
Correct |
2 ms |
500 KB |
Output is correct |
7 |
Incorrect |
2 ms |
536 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
360 KB |
Output is correct |
3 |
Correct |
2 ms |
472 KB |
Output is correct |
4 |
Correct |
2 ms |
492 KB |
Output is correct |
5 |
Correct |
2 ms |
496 KB |
Output is correct |
6 |
Correct |
2 ms |
500 KB |
Output is correct |
7 |
Incorrect |
2 ms |
536 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
360 KB |
Output is correct |
3 |
Correct |
2 ms |
472 KB |
Output is correct |
4 |
Correct |
2 ms |
492 KB |
Output is correct |
5 |
Correct |
2 ms |
496 KB |
Output is correct |
6 |
Correct |
2 ms |
500 KB |
Output is correct |
7 |
Incorrect |
2 ms |
536 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |