Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize ("O3")
- #pragma GCC target ("sse4")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- template <class T>
- using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
- template <class T>
- using ordered_multiset = __gnu_pbds::tree<T, __gnu_pbds::null_type, less_equal<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
- #define PI atan2(0, -1)
- #define epsilon 1e-9
- #define INF 5e18
- #define MOD 1000000007
- #define mp make_pair
- #define pb push_back
- #define f first
- #define s second
- #define lb lower_bound
- #define ub upper_bound
- #define ll long long
- #define ld long double
- #define x first
- #define y second
- struct rat {
- ll n, d;
- rat() : n(0), d(1) {}
- rat(ll x) : n(x), d(1) {}
- rat(ll _n, ll _d) : n(_n), d(_d) {
- if (n == 0) d = 1;
- else {
- ll g = __gcd(abs(n), abs(d));
- n /= g, d /= g;
- if (d<0) n*=-1, d*=-1;
- }
- }
- rat(const rat& r) : n(r.n), d(r.d) {}
- rat operator -() const { return rat(-n, d); }
- operator ld() const { return double(n) / d; }
- template<typename T> rat operator +(T o) const {
- rat r(o); return rat(n*r.d+r.n*d,d*r.d); }
- template<typename T> rat operator -(T o) const {
- return (*this)+(-o); }
- template<typename T> rat operator *(T o) const {
- rat r(o); return rat(n*r.n, d*r.d); }
- template<typename T> rat operator /(T o) const {
- rat r(o); return rat(n*r.d, d*r.n); }
- template<typename T> bool operator ==(T o) const {
- rat r(o); return n == r.n && d == r.d; }
- template<typename T> bool operator !=(T o) const {
- return !((*this) == o); }
- template<typename T> bool operator <(T o) const {
- rat r(o); return n*r.d < r.n*d; }
- template<typename T> bool operator >(T o) const {
- return !(*this == o) && !(*this < o); }
- template<typename T> bool operator <=(T o) const {
- return *this < o || *this == o; }
- template<typename T> bool operator >=(T o) const {
- return *this > o || *this == o; }
- };
- istream& operator >>(istream& is, rat& r) { ll a; is >> a; r = rat(a); return is; }
- /* HPEND */
- /* HPSTART {"title": "Point", "section": "Geometry", "snippet": "point"} */
- typedef rat cord;
- typedef pair<cord, cord> point;
- cord dot(point a, point b) {
- return a.x*b.x + a.y*b.y; }
- cord cross(point a, point b) {
- return a.x*b.y - a.y*b.x; }
- cord norm(point p) { return dot(p, p); }
- ld abs(point p) { return sqrt(norm(p)); }
- point conj(point p) { return point(p.x,-p.y); }
- point operator +(const point& a, const point& b) {
- return point(a.x+b.x, a.y+b.y); }
- point operator -(const point& a, const point& b) {
- return point(a.x-b.x, a.y-b.y); }
- point operator *(const cord& l, const point& r) {
- return point(l*r.x, l*r.y); }
- point operator *(const point& l, const cord& r) {
- return r*l; }
- point operator /(const point& p, const cord& s) {
- return point(p.x/s, p.y/s); }
- /* HPEND */
- /* HPSTART {"title": "Lines and Segments", "section": "Geometry", "snippet": "lines"} */
- struct line {
- point p, d;
- line() {}
- line(point a, point b) : p(a), d(b-a) {}
- point eval(cord t) { return p + t*d; }
- operator bool() { return d != point(); }
- };
- struct seg {
- line l;
- seg() {}
- seg(point a, point b) : l(a, b) {}
- };
- // be careful with precision here
- bool on_line(line l, point p, cord& t) {
- if (!l) {
- t = 0; return p == l.p;
- }
- if (cross(p - l.p, l.d) != 0) return false;
- t = dot(p - l.p, l.d) / norm(l.d);
- return true;
- }
- bool on_segment(seg s, point p) {
- if (!s.l) return p == s.l.p;
- cord t;
- // if (!on_line(s.l, p, t)) return false;
- point a = s.l.p, b = s.l.p+s.l.d;
- return p.x >= min(a.x,b.x) && p.x <= max(a.x,b.x) &&
- p.y >= min(a.y,b.y) && p.y <= max(a.y,b.y);
- }
- bool intersect(line l1, line l2, point& p) {
- if (!l2) swap(l1, l2);
- if (!l1) {
- p = l1.p; cord t;
- return on_line(l2, l1.p, t);
- }
- if (cross(l1.d, l2.d) == 0) return false;
- cord i = cross(l2.p-l1.p, l2.d) / cross(l1.d, l2.d);
- p = l1.p + i*l1.d;
- return true;
- }
- bool intersect(seg s1, seg s2, point& p) {
- if (!intersect(s1.l, s2.l, p)) return false;
- return on_segment(s1, p) && on_segment(s2, p);
- }
- bool overlap(seg s1, seg s2, seg& r) {
- if (cross(s1.l.d, s2.l.d) != 0) return false;
- cord t0, t1;
- if (!on_line(s1.l, s2.l.p, t0)) return false;
- on_line(s1.l, s2.l.p+s2.l.d, t1);
- if (t0>t1) swap(t0,t1);
- cord a = max(cord(0), t0), b = min(cord(1), t1);
- if (a <= b) {
- r = seg(s1.l.eval(a), s1.l.eval(b));
- return true;
- }
- return false;
- }
- int N;
- pair<long long, long long> points [210];
- vector<seg> polygon;
- bool allowed [210][210];
- long long costs [210][210], dp [210][210], ret = INF/5;
- point zero(0, 0);
- chrono::time_point<chrono::high_resolution_clock> startTime;
- bool tooLate(){
- auto endTime = chrono::high_resolution_clock::now();
- auto duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime);
- return duration.count() > 2500;
- }
- long long solveIt(int st, int en){
- if(dp[st][en] != -1) return dp[st][en];
- if(en-st <= 2) return dp[st][en] = 0;
- dp[st][en] = INF/5;
- for(int m = st+1; m <= en-1; m++)
- if(allowed[st][m] && allowed[m][en])
- dp[st][en] = min(dp[st][en], solveIt(st, m)+solveIt(m, en)+costs[st][m]+costs[m][en]);
- return dp[st][en];
- }
- int main(){
- //freopen("sort.in", "r", stdin); freopen("sort.out", "w", stdout);
- ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10);
- startTime = chrono::high_resolution_clock::now();
- cin >> N; for(int i = 0; i < N; i++) cin >> points[i].f >> points[i].s;
- for(int i = 0; i < N; i++){
- point a, b;
- a.x = points[i].f, a.y = points[i].s;
- b.x = points[(i+1)%N].f, b.y = points[(i+1)%N].s;
- polygon.pb(seg(a, b));
- allowed[i][i] = true; allowed[i][(i+1)%N] = true;
- for(int j = 0; j < N; j++) dp[i][j] = -1;
- }
- for(int u = 0; u < N; u++)
- for(int v = 0; v <= u; v++){
- if(u == v || u == (v+1)%N || v == (u+1)%N){
- allowed[u][v] = true;
- costs[u][v] = 0;
- continue;
- }
- costs[u][v] = costs[v][u] = pow(points[u].f-points[v].f, 2)+pow(points[u].s-points[v].s, 2);
- vector<seg> segments;
- segments.pb(seg(point(points[u].f, points[u].s), point(points[v].f, points[v].s)));
- assert((int)segments.size() == 1);
- bool ok = true;
- for(int i = 0; i < (int)segments.size(); i++)
- for(int j = 0; j < polygon.size(); j++){
- assert(i == 0);
- //if(tooLate()) assert(false);
- point p; seg temp;
- if(overlap(segments[i], polygon[j], temp) && temp.l.d != zero){
- ok = false;
- break;
- }
- if(intersect(segments[i], polygon[j], p) && p != segments[i].l.p && p != segments[i].l.p+segments[i].l.d){
- ok = false;
- break;
- }
- }
- for(int i = 0; i < (int)segments.size(); i++){
- for(int iter = 1; iter < 2; iter++){
- assert(i == 0);
- //if(tooLate()) assert(false);
- point m = segments[i].l.p+(segments[i].l.d*iter)/2;
- point oof; oof.x = m.x+100000; oof.y = m.y+99999;
- seg dummy(m, oof);
- int numInter = 0;
- point p;
- for(seg s : polygon) numInter += intersect(s, dummy, p);
- ok &= numInter&1;
- }
- }
- allowed[u][v] = allowed[v][u] = ok;
- //cout << points[u].f << ' ' << points[u].s << ' ' << points[v].f << ' ' << points[v].s << " | " << allowed[u][v] << endl;
- }
- ret = solveIt(0, N-1);
- if(ret == INF/5) cout << "impossible\n";
- else cout << ret << '\n';
- return 0;
- }
- /******************************
- Kateba ii dake no hanashi darou
- Success is only a victory away
- - No Game No Life Opening
- ******************************/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement