Submission #83966

---

Source Code Expand

#include <iostream>//{{{
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <bitset>
#include <utility>
#include <algorithm>
#include <numeric>
#include <complex>
#include <functional>
#include <memory>
#include <sstream>
#include <iomanip>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cfloat>
#include <cassert>
#include <ctime>
#include <cctype>//}}}
#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)//{{{
#define rep(i,n) REP(i,0,n)
#define repsz(i,v) rep(i,sz(v))
#define let(v, x) __typeof(x) v = (x)
#define foreach(i,v) for(let(i, (v).begin());i!=(v).end();i++)
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) ((int)(x).size()) //}}}
using namespace std;//{{{
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef pair<int,pii> pipii;//}}}
template<typename T> ostream& out(T b, T e, ostream& os=cout){ //{{{
    for(; b != e; ++b != e && os << ", ")os << *b; return os;
}
template<class T> T mineq(T &a, const T &b){ return a = min(a, b); }
template<class T> T maxeq(T &a, const T &b){ return a = max(a, b); } //}}}

// 幾何.//{{{
typedef long double Dbl;
const Dbl INF = 1E40;
const Dbl EPS = 1E-11;
const Dbl PI = acos(Dbl(-1));
typedef complex<Dbl> P;
#define X real()
#define Y imag()
namespace std {//{{{
    bool operator < (const P& a, const P& b) {
        return a.X == b.X ? a.Y < b.Y : a.X < b.X;
    }
    istream& operator >> (istream& is, P& p) {
        is >> p.X >> p.Y;
        return is;
    }
}//}}}
typedef pair<P, P> L;
//}}}
// 基本.//{{{
inline int sgn(const Dbl& r){ return (r > EPS) - (r < -EPS); }
inline Dbl dot(const P& a, const P& b) { return real(conj(a)*b); }
inline Dbl cross(const P& a, const P& b) { return imag(conj(a)*b); }
inline P vec(const L& l){ return l.snd - l.fst; }

enum CCW{FRONT = 1, RIGHT = 2, BACK = 4, LEFT = 8, ON = 16, };
inline int rev_ccw(const P& a, P b, P c){//{{{
    b -= a; c -= a;
    Dbl cr = cross(c, b);
    if(sgn(cr) == 0){
        if(sgn(dot(c, b)) < 0) return BACK;
        if(sgn(norm(c) - norm(b)) < 0) return FRONT;
        return ON;
    }
    return cr > 0 ? RIGHT : LEFT;
}//}}}
inline int ccw(const L& l, const P& p){//{{{
    int res = rev_ccw(l.fst, p, l.snd);
    if(res & RIGHT) return LEFT;
    if(res & LEFT) return RIGHT;
    return res;
}//}}}
//}}}
// 点, 直線, 線分.//{{{
// 平行, 同一直線判定.//{{{
inline bool sameL(const L& l, const L& m){
    return sgn(cross(vec(l), vec(m))) == 0 && sgn(cross(vec(l), m.fst-l.fst)) == 0;
}
// AOJ 0021
inline bool paraL(const L& l, const L& m){
    return sgn(cross(vec(l), vec(m))) == 0;
}
//}}}
// 交差判定.//{{{
// iLS は <= を < にすれば strict に.
// iSS は ON 判定を消せば strict に.
inline bool iLL(const L& l, const L& m){
    return !sameL(l, m) && sgn(cross(vec(l), vec(m))) != 0;
}
inline bool iLS(const L& l, const L& s){
    return sgn(cross(vec(l), s.fst-l.fst)) * sgn(cross(vec(l), s.snd-l.fst)) <= 0;
}
inline bool iLSs(const L& l, const L& s){
    return sgn(cross(vec(l), s.fst-l.fst)) * sgn(cross(vec(l), s.snd-l.fst)) < 0;
}
inline bool iLP(const L& l, const P& p){ return ccw(l, p) & (FRONT | BACK | ON); }
inline bool iSP(const L& s, const P& p){ return ccw(s, p) & ON; }
// AOJ 2402, AOJ 1157, AOJ 1183, AOJ 1171
inline bool iSS(const L& s, const L& t){
    int cw1 = ccw(s, t.fst) | ccw(s, t.snd);
    int cw2 = ccw(t, s.fst) | ccw(t, s.snd);
    return ((cw1 | cw2) & ON) || ((cw1 & cw2) == (LEFT | RIGHT));
}
// AOJ 2009, AOJ 1171
inline bool iSSs(const L& s, const L& t){
    int cw1 = ccw(s, t.fst) | ccw(s, t.snd);
    int cw2 = ccw(t, s.fst) | ccw(t, s.snd);
    return ((cw1 & cw2) == (LEFT | RIGHT));
}
//}}}
// 距離.//{{{
// AOJ 0153, AOJ 2402, AOJ 1157, AOJ 2009
inline Dbl dPP(const P& p, const P& q){ return abs(p - q); }
// AOJ 2402
inline Dbl dLP(const L& l, const P& p){
    if(!(ccw(l, p) & (LEFT | RIGHT))) return 0; // for "-0"
    return abs(cross(vec(l), p - l.fst)) / abs(vec(l));
}
// AOJ 0153, AOJ 2402, AOJ 1157
inline Dbl dSP(const L& s, const P& p){
    if(sgn(dot( vec(s), p - s.fst)) <= 0) return dPP(p, s.fst);
    if(sgn(dot(-vec(s), p - s.snd)) <= 0) return dPP(p, s.snd);
    return dLP(s, p);
}
inline Dbl dLL(const L& l, const L& m){
    return iLL(l, m) ? 0 : dLP(l, m.fst);
}
inline Dbl dLS(const L& l, const L& s){
    return iLS(l, s) ? 0 : min(dLP(l, s.fst), dLP(l, s.snd));
}
// AOJ 2402, 1157
inline Dbl dSS(const L& s, const L& t){
    return iSS(s, t) ? 0 :
        min( min(dSP(s, t.fst), dSP(s, t.snd)),
                min(dSP(t, s.fst), dSP(t, s.snd)));
}
//}}}
// 交点, 射影, 反射.//{{{
// AOJ 2009
inline P pLL(const L& l, const L& m){
    if(sameL(l, m)) return l.fst;
    // if(paraL(l, m)) assert(false);
    Dbl A = cross(vec(m), vec(l));
    Dbl B = cross(vec(m), m.snd - l.fst);
    return l.fst + B / A * vec(l);
}
// p から l に下ろした垂線の足.
inline P hLP(const L& l, const P& p){
    return l.fst + dot(p - l.fst, vec(l)) / norm(vec(l)) * vec(l);
}
// p の l で対称な点.
// AOJ 0081, AOJ 1171
inline P refLP(const L& l, const P& p){
    return Dbl(2) * hLP(l, p) - p;
}
//}}}
//}}}


// 無向の場合は頂点を倍にする.
typedef int Cap;
typedef double Cost;
struct E{
    int src, dst;
    Cap cap;
    Cost cost;
    E(int src, int dst, Cap cap=0, Cost cost=0):
        src(src), dst(dst), cap(cap), cost(cost){}
};
bool operator<(const E &e, const E &f){
    return e.cost != f.cost ? e.cost > f.cost : // !! INVERSE !!
        e.cap != f.cap ? e.cap < f.cap :
        e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<E> V;
typedef vector<V> G;
typedef vector<Cap> CapArr;
typedef vector<CapArr> CapMat;
typedef vector<Cost> CostArr;
typedef vector<CostArr> CostMat;

void addEdge(G &g, int src, int dst, Cap cap, Cost cost){
    g[src].pb(E(src, dst, cap, cost));
    g[dst].pb(E(dst, src,   0,-cost));
}

#define RESIDUE(u, v) (cap[u][v] - flow[u][v])
#define RCOST(u, v) (cost[u][v] + h[u] - h[v])
pair<Cost, Cap> minimumCostFlow(const G &g, int s, int t){//{{{
    const int n = g.size();
    CapMat cap(n, CapArr(n)), flow(n, CapArr(n));
    CostMat cost(n, CostArr(n));
    rep(u, n) foreach(e, g[u]){
        cap[e->src][e->dst] += e->cap;
        cost[e->src][e->dst] += e->cost;
    }
    pair<Cost, Cap> total;
    vector<Cost> h(n);

    for(Cap F=INF; F>0; ){
        vector<Cost> d(n, INF); d[s] = 0;
        vector<int> p(n, -1);
        priority_queue<E> pq; // e < f <=> e.cost > f.cost
        for(pq.push(E(-2, s)); !pq.empty(); ){
            E e = pq.top(); pq.pop();
            if(p[e.dst] != -1) continue;
            p[e.dst] = e.src;
            foreach(f, g[e.dst]) if(RESIDUE(f->src, f->dst) > 0){
                if(d[f->dst] > d[f->src] + RCOST(f->src, f->dst)){
                    d[f->dst] = d[f->src] + RCOST(f->src, f->dst);
                    pq.push(E(f->src, f->dst, 0, d[f->dst]));
                }
            }
        }
        if(p[t] == -1) break;
        Cap f = F;
        for(int u=t; u!=s; u=p[u])
            f = min(f, RESIDUE(p[u], u));
        for(int u=t; u!=s; u=p[u]){
            total.first += f * cost[p[u]][u];
            flow[p[u]][u] += f; flow[u][p[u]] -= f;
        }
        F -= f;
        total.second += f;
        rep(u, n) h[u] += d[u];
    }
    return total;
}//}}}

bool solve(){
    int n;
    cin >> n;
    vector<P> in(n);
    rep(i, n) cin >> in[i];
        double adj[n][n];
        L y_line = L(P(0, 0), P(0, 1000));
        rep(i, n) rep(j, n){
            if(i == j) adj[i][j] = dLP(y_line, in[i]);
            else       adj[i][j] = dPP(refLP(y_line, in[i]), in[j]);
        }
    if(n <= 20){//{{{
        double dp[1<<n];
        rep(A, 1<<n) dp[A] = INF;
        dp[0] = 0;
        rep(A, 1<<n){
            rep(i, n) if(!(A>>i&1)){
                mineq(dp[A|(1<<i)], dp[A] + adj[i][i]);
                rep(j, i) if(!(A>>j&1))
                    mineq(dp[A|(1<<i)|(1<<j)], dp[A] + adj[i][j]);
            }
        }
        cout << dp[(1<<n)-1] << endl;
    }else{//}}}
        G g(2*n+2);
        rep(i, n) rep(j, n){
            addEdge(g, i, j+n, 1, dPP(refLP(y_line, in[i]), in[j]));
        }
        rep(i, n){
            addEdge(g, 2*n, i, 1, 0);
            addEdge(g, i+n, 2*n+1, 1, 0);
        }
        cout << minimumCostFlow(g, 2*n, 2*n+1).fst/2 << endl;
    }
    return true;
}
int main(){
    //cin.tie(0);
    //ios_base::sync_with_stdio(0);
    cout.setf(ios::fixed); cout.precision(10);
    solve();
    return 0;
}
// vim:set foldmethod=marker commentstring=//%s:

Submission Info

Compile Error

./Main.cpp: In function ‘std::pair<double, int> minimumCostFlow(const G&, int, int)’:
./Main.cpp:223: warning: overflow in implicit constant conversion

Judge Result