| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 529058 |
2022-02-22T04:39:00 Z |
wiwiho |
Fences (JOI18_fences) |
C++14 |
|
1 ms |
316 KB |
#include<bits/stdc++.h>
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
#define eb emplace_back
#define pob pop_back()
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
ld eps = 1e-6;
ostream& operator<<(ostream& o, pdd p){
return o << '(' << p.F << ',' << p.S << ')';
}
pdd operator+(pdd a, pdd b){
return mp(a.F + b.F, a.S + b.S);
}
pdd operator-(pdd a, pdd b){
return mp(a.F - b.F, a.S - b.S);
}
pdd operator*(ld a, pdd b){
return mp(a * b.F, a * b.S);
}
pdd operator-(pdd a){
return mp(-a.F, -a.S);
}
ld cross(pdd a, pdd b){
return a.F * b.S - a.S * b.F;
}
ld dot(pdd a, pdd b){
return a.F * b.F + a.S * b.S;
}
int ori(pdd a, pdd b){
ld tmp = cross(a, b);
if(abs(tmp - 0) <= eps) return 0;
else if(tmp > 0) return 1;
else return -1;
}
bool intersect(pdd a, pdd b, pdd c, pdd d){
return ori(b - a, c - a) * ori(b - a, d - a) < 0 && ori(d - c, a - c) * ori(d - c, b - c) < 0;
}
ld abs(pdd a){
return sqrt(a.F * a.F + a.S * a.S);
}
ld abs2(pdd a){
return a.F * a.F + a.S * a.S;
}
pdd proj(pdd p, pdd a, pdd b){
return cross(p - a, b - a) / abs2(b - a) * (b - a);
}
bool canproj(pdd p, pdd a, pdd b){
if(abs(a - b) < eps) return false;
return dot(b - a, p - a) >= -eps && dot(a - b, p - b) >= -eps;
}
int n;
int S;
vector<pair<pdd, pdd>> seg;
vector<pdd> now;
vector<int> id;
vector<bool> use;
ld sum = 0;
ld ans = 1e87;
vector<pair<pdd, pdd>> border;
bool check(pdd a, pdd b){
for(int i = 0; i + 1 < now.size(); i++){
if(intersect(now[i], now[i + 1], a, b)) return false;
}
for(auto i : border){
if(intersect(i.F, i.S, a, b)) return false;
}
return true;
}
bool inside(){
pdd v = mp(1, 48763);
int cnt = 0;
for(int i = 0; i < now.size(); i++){
int nxt = (i + 1) % now.size();
if(ori(v, now[i]) * ori(v, now[nxt]) < 0 &&
ori(now[nxt] - now[i], v - now[i]) * ori(now[nxt] - now[i], -now[i]) < 0) cnt++;
}
return cnt % 2;
}
pair<pdd, pdd> owo(int lstx, int nxtx){
auto lst = seg[lstx], nxt = seg[nxtx];
vector<pair<pdd, pdd>> tmp;
tmp.eb(mp(lst.F, nxt.F));
tmp.eb(mp(lst.F, nxt.S));
tmp.eb(mp(lst.S, nxt.F));
tmp.eb(mp(lst.S, nxt.S));
auto tryproj = [&](pdd p, pdd a, pdd b, int t){
if(canproj(p, a, b)){
if(t == 0) tmp.eb(mp(p, proj(p, a, b)));
else tmp.eb(mp(proj(p, a, b), p));
}
};
tryproj(lst.F, nxt.F, nxt.S, 0);
tryproj(lst.S, nxt.F, nxt.S, 0);
tryproj(nxt.F, lst.F, lst.S, 1);
tryproj(nxt.S, lst.F, lst.S, 1);
sort(iter(tmp), [&](pair<pdd, pdd> a, pair<pdd, pdd> b){
return abs(a.F - a.S) > abs(b.F - b.S) + eps;
});
for(auto i : tmp){
if(check(i.F, i.S)) return i;
}
return mp(mp(1e87, 1e87), mp(1e87, 1e87));
}
void f(){
//cerr << "test ";
//printv(now, cerr);
if(id.size() >= 2){
auto tmp = owo(id.back(), id.front());
if(tmp.F.F == 1e87) goto qq;
sum += abs(tmp.F - tmp.S);
now.eb(tmp.F);
now.eb(tmp.S);
if(inside()) ans = min(ans, sum);
now.pob;
now.pob;
sum -= abs(tmp.F - tmp.S);
}
qq:;
for(int i = 0; i < n; i++){
if(use[i]) continue;
if(id.empty()){
id.eb(i);
use[i] = true;
f();
use[i] = false;
id.pob;
continue;
}
auto tmp = owo(id.back(), i);
if(tmp.F.F == 1e87) continue;
now.eb(tmp.F);
now.eb(tmp.S);
sum += abs(tmp.F - tmp.S);
id.eb(i);
use[i] = true;
f();
use[i] = false;
id.pob;
sum -= abs(tmp.F - tmp.S);
now.pob;
now.pob;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cerr.tie(0);
cin >> n;
cin >> S;
seg.resize(n);
for(int i = 0; i < n; i++){
cin >> seg[i].F.F >> seg[i].F.S >> seg[i].S.F >> seg[i].S.S;
}
seg.eb(mp(mp(S, S), mp(S, S)));
seg.eb(mp(mp(S, -S), mp(S, -S)));
seg.eb(mp(mp(-S, S), mp(-S, S)));
seg.eb(mp(mp(-S, -S), mp(-S, -S)));
n += 4;
use.resize(n);
border.eb(mp(mp(S, S), mp(S, -S)));
border.eb(mp(mp(S, -S), mp(-S, -S)));
border.eb(mp(mp(-S, -S), mp(-S, S)));
border.eb(mp(mp(-S, S), mp(S, S)));
border.eb(mp(mp(S, S), mp(-S, -S)));
border.eb(mp(mp(S, -S), mp(-S, S)));
f();
cout << fixed << setprecision(20) << ans << "\n";
return 0;
}
Compilation message
fences.cpp: In function 'bool check(pdd, pdd)':
fences.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i = 0; i + 1 < now.size(); i++){
| ~~~~~~^~~~~~~~~~~~
fences.cpp: In function 'bool inside()':
fences.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i = 0; i < now.size(); i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
