p303.in1
======================
13
0 6 3 6 9
0 0 4 2 8
4 4 6 6 7
2 4 3 6 1
3 6 6 6 1
6 4 6 6 1
4 2 6 4 1
0 0 0 6 6
2 2 2 4 1
2 2 4 2 1
0 6 2 4 5
2 4 4 4 4
4 2 4 4 3
3 3 2 5

=================
p303.cpp
======================
#include <bits/stdc++.h>
// #include <coding_library/geometry/point.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

using coord_t = double;

struct Point {
    static constexpr coord_t eps = 1e-9;
    static inline const coord_t PI = acos((coord_t)-1.0);

    coord_t x, y;
    Point(coord_t x = 0, coord_t y = 0) : x(x), y(y) {}

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(coord_t c) const { return Point(x * c, y * c); }
    Point operator/(coord_t c) const { return Point(x / c, y / c); }

    coord_t operator*(const Point& p) const { return x * p.x + y * p.y; }
    coord_t operator^(const Point& p) const { return x * p.y - y * p.x; }

    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
    bool operator!=(const Point& p) const { return x != p.x || y != p.y; }
    bool operator<(const Point& p) const {
        return x != p.x ? x < p.x : y < p.y;
    }
    bool operator>(const Point& p) const {
        return x != p.x ? x > p.x : y > p.y;
    }
    bool operator<=(const Point& p) const {
        return x != p.x ? x < p.x : y <= p.y;
    }
    bool operator>=(const Point& p) const {
        return x != p.x ? x > p.x : y >= p.y;
    }

    coord_t norm2() const { return x * x + y * y; }
    coord_t norm() const { return sqrt(norm2()); }
    coord_t angle() const { return atan2(y, x); }

    Point rotate(coord_t a) const {
        return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    Point perp() const { return Point(-y, x); }
    Point unit() const { return *this / norm(); }
    Point normal() const { return perp().unit(); }
    Point project(const Point& p) const {
        return *this * (*this * p) / norm2();
    }
    Point reflect(const Point& p) const {
        return *this * 2 * (*this * p) / norm2() - p;
    }

    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << p.x << ' ' << p.y;
    }
    friend istream& operator>>(istream& is, Point& p) {
        return is >> p.x >> p.y;
    }

    friend int ccw(const Point& a, const Point& b, const Point& c) {
        coord_t v = (b - a) ^ (c - a);
        if(-eps <= v && v <= eps) {
            return 0;
        } else if(v > 0) {
            return 1;
        } else {
            return -1;
        }
    }

    friend bool point_on_segment(
        const Point& a, const Point& b, const Point& p
    ) {
        return ccw(a, b, p) == 0 && p.x >= min(a.x, b.x) - eps &&
               p.x <= max(a.x, b.x) + eps && p.y >= min(a.y, b.y) - eps &&
               p.y <= max(a.y, b.y) + eps;
    }

    friend bool point_in_triangle(
        const Point& a, const Point& b, const Point& c, const Point& p
    ) {
        int d1 = ccw(a, b, p);
        int d2 = ccw(b, c, p);
        int d3 = ccw(c, a, p);
        return (d1 >= 0 && d2 >= 0 && d3 >= 0) ||
               (d1 <= 0 && d2 <= 0 && d3 <= 0);
    }

    friend Point line_line_intersection(
        const Point& a1, const Point& b1, const Point& a2, const Point& b2
    ) {
        return a1 +
               (b1 - a1) * ((a2 - a1) ^ (b2 - a2)) / ((b1 - a1) ^ (b2 - a2));
    }

    friend bool collinear(const Point& a, const Point& b) {
        return abs(a ^ b) < eps;
    }

    friend Point circumcenter(const Point& a, const Point& b, const Point& c) {
        Point mid_ab = (a + b) / 2.0;
        Point mid_ac = (a + c) / 2.0;
        Point perp_ab = (b - a).perp();
        Point perp_ac = (c - a).perp();
        return line_line_intersection(
            mid_ab, mid_ab + perp_ab, mid_ac, mid_ac + perp_ac
        );
    }

    friend coord_t arc_area(
        const Point& center, coord_t r, const Point& p1, const Point& p2
    ) {
        coord_t theta1 = (p1 - center).angle();
        coord_t theta2 = (p2 - center).angle();
        if(theta2 < theta1 - eps) {
            theta2 += 2 * PI;
        }

        coord_t d_theta = theta2 - theta1;
        coord_t cx = center.x, cy = center.y;
        coord_t area = r * cx * (sin(theta2) - sin(theta1)) -
                       r * cy * (cos(theta2) - cos(theta1)) + r * r * d_theta;
        return area / 2.0;
    }

    friend vector<Point> intersect_circles(
        const Point& c1, coord_t r1, const Point& c2, coord_t r2
    ) {
        Point d = c2 - c1;
        coord_t dist = d.norm();

        if(dist > r1 + r2 + eps || dist < abs(r1 - r2) - eps || dist < eps) {
            return {};
        }

        coord_t a = (r1 * r1 - r2 * r2 + dist * dist) / (2 * dist);
        coord_t h_sq = r1 * r1 - a * a;
        if(h_sq < -eps) {
            return {};
        }
        if(h_sq < 0) {
            h_sq = 0;
        }
        coord_t h = sqrt(h_sq);

        Point mid = c1 + d.unit() * a;
        Point perp_dir = d.perp().unit();

        if(h < eps) {
            return {mid};
        }
        return {mid + perp_dir * h, mid - perp_dir * h};
    }

    friend optional<Point> intersect_ray_segment(
        const Point& ray_start, const Point& ray_through, const Point& seg_a,
        const Point& seg_b
    ) {
        Point ray_dir = ray_through - ray_start;
        if(ray_dir.norm2() < Point::eps) {
            return {};
        }
        Point seg_dir = seg_b - seg_a;
        coord_t denom = ray_dir ^ seg_dir;
        if(fabs(denom) < eps) {
            return {};
        }
        coord_t t = ((seg_a - ray_start) ^ seg_dir) / denom;
        if(t < eps) {
            return {};
        }
        coord_t s = ((seg_a - ray_start) ^ ray_dir) / denom;
        if(s < eps || s > 1 - eps) {
            return {};
        }
        return ray_start + ray_dir * t;
    }
};

int n;
vector<Point> seg_a, seg_b;
vector<int> seg_v;
Point hq1, hq2;

void read() {
    cin >> n;
    seg_a.resize(n);
    seg_b.resize(n);
    seg_v.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> seg_a[i] >> seg_b[i] >> seg_v[i];
    }
    cin >> hq1 >> hq2;
}

void solve() {
    // The province borders form a planar subdivision: segments only ever touch
    // at shared endpoints, so the vertices of our graph are exactly the segment
    // endpoints and every segment is a single edge between two of them. Any
    // closed walk that visits distinct vertices is automatically a simple
    // polygon, so "build a simple polygon out of segments" just means "pick a
    // simple cycle of edges".
    //
    // A point is inside a simple polygon iff a ray from it crosses the boundary
    // an odd number of times. Cast an upward vertical ray from each
    // headquarters; for an edge let c1/c2 be whether it crosses the ray of hq1
    // / hq2. Over a whole cycle the inside/outside parity of hqk is the XOR of
    // its ck over the used edges. We need the wall to separate the two
    // headquarters, i.e. exactly one of them inside, i.e. parity(hq1) !=
    // parity(hq2). Since parity(hq1) ^ parity(hq2) = XOR of (c1 ^ c2) over the
    // cycle, we collapse the two parities into a single edge label par = c1 ^
    // c2 and look for a minimum cost cycle with odd total label.
    //
    // A minimum cost odd-label closed walk is always a single simple cycle:
    // with strictly positive weights any extra even sub-loop could be dropped.
    // We find it with a parity-doubled Dijkstra. Node (v, p) means "at vertex v
    // having accumulated label parity p"; an edge with label par links (v, p)
    // to (w, p ^ par). For each source s the shortest (s, 0) -> (s, 1) path is
    // an odd cycle through s, and the minimum over all sources is the answer.
    // We then rerun Dijkstra from the winning source to recover the segments.

    map<pair<long long, long long>, int> idx;
    auto get_idx = [&](const Point& p) -> int {
        pair<long long, long long> key = {llround(p.x), llround(p.y)};
        auto it = idx.find(key);
        if(it != idx.end()) {
            return it->second;
        }

        int id = idx.size();
        idx[key] = id;
        return id;
    };

    auto crosses_up_ray = [&](const Point& a, const Point& b,
                              const Point& h) -> bool {
        bool sa = a.x > h.x, sb = b.x > h.x;
        if(sa == sb) {
            return false;
        }

        coord_t t = (h.x - a.x) / (b.x - a.x);
        coord_t y_at_cross = a.y + t * (b.y - a.y);
        return y_at_cross > h.y;
    };

    int m = 0;
    vector<int> eu(n), ev(n), epar(n);
    for(int i = 0; i < n; i++) {
        eu[i] = get_idx(seg_a[i]);
        ev[i] = get_idx(seg_b[i]);
        int c1 = crosses_up_ray(seg_a[i], seg_b[i], hq1);
        int c2 = crosses_up_ray(seg_a[i], seg_b[i], hq2);
        epar[i] = c1 ^ c2;
        m = max({m, eu[i] + 1, ev[i] + 1});
    }

    vector<vector<tuple<int, int, int>>> adj(m);
    for(int i = 0; i < n; i++) {
        adj[eu[i]].push_back({ev[i], seg_v[i], i});
        adj[ev[i]].push_back({eu[i], seg_v[i], i});
    }

    const long long inf = numeric_limits<long long>::max();
    auto dijkstra = [&](int src, vector<long long>& dist,
                        vector<pair<int, int>>& par) {
        dist.assign(2 * m, inf);
        par.assign(2 * m, {-1, -1});
        priority_queue<
            pair<long long, int>, vector<pair<long long, int>>,
            greater<pair<long long, int>>>
            pq;
        dist[src] = 0;
        pq.push({0, src});
        while(!pq.empty()) {
            auto [d, node] = pq.top();
            pq.pop();
            if(d > dist[node]) {
                continue;
            }

            int v = node / 2, p = node & 1;
            for(auto [w, cost, seg]: adj[v]) {
                int to = 2 * w + (p ^ epar[seg]);
                if(d + cost < dist[to]) {
                    dist[to] = d + cost;
                    par[to] = {node, seg};
                    pq.push({dist[to], to});
                }
            }
        }
    };

    long long best = inf;
    int best_src = -1;
    vector<long long> dist;
    vector<pair<int, int>> par;
    for(int s = 0; s < m; s++) {
        dijkstra(2 * s, dist, par);
        if(dist[2 * s + 1] < best) {
            best = dist[2 * s + 1];
            best_src = s;
        }
    }

    dijkstra(2 * best_src, dist, par);
    vector<int> used;
    int node = 2 * best_src + 1;
    while(par[node].first != -1) {
        used.push_back(par[node].second + 1);
        node = par[node].first;
    }

    cout << best << "\n";
    cout << used.size() << "\n";
    cout << used << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p303.ans1
======================
6
6
9 10 4 7 5 6

=================
statement.txt
======================
303. Great Berland Wall
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Berland is in civil war. This time peaceful solution is hardly possible. Collapse to the East and West Berland is inevitable! Commander-in-chief of grey, general Kruglyakovski, has made a decision to hasten the process and to surround his headquarters with a wall (which later be called Great Berland Wall). The wall should be built in such a way that the enemy's headquarters would stay at the other side of the wall.

Looking to the Berland map general Kruglyakovski noticed that the country consists of a number of provinces. Each province has the form of a simple (but possibly not convex) polygon. The country of Berland has no enclaves and does not contain any enclaves of other countries inside, i.e. it is possible to get from one point of Berland to another without leaving the country. The "passability" is known for each segment of the border of each province. "Passability" is the maximum speed the soldier can move with along the corresponding segment.

General Kruglyakovski decided that the wall will pass only along the borders of the provinces and will have the form of a simple polygon. He sent the group of soldiers to build the wall during the night. And you got a task to find such a form and position of the wall that the time of building would be minimal. The time of building of the section of the wall is equal to the "passability" of the corresponding border segment. The time of building of the wall is equal to the sum of building of its segments.

Input
The first line of the input file contains the number of segments of province borders — integer number N (5≤ N≤ 300). The segments themselves follow further. Each segment is defined by five numbers x1, y1, x2, y2, v, where (x1, y1) and (x2, y2) are the coordinates of the segment end points and the integer number v (1 ≤ v ≤ 1000) is the "passability". Any pair of segments has not more than one common point and this point can only be their common end-point. Input data finishes with one more quadruple of numbers X1, Y1, X2, Y2, where (X1, Y1), (X2, Y2) are the coordinates of headquarters of the general Kruglyakovski and his opponent correspondingly. Both headquarters are situated strictly inside one of the provinces. The headquarters are situated in different provinces. All coordinates in the input are integer numbers less than 104 by the absolute value.

Output
Write to the first line of the output the total time of building of the wall. Write to the second line the number of border segments the wall will occupy. To the next line write the sequence of the numbers of the segments. The segments are numbered in the order they appear in the input. If there are several solutions choose any of them.

Example(s)
sample input
sample output
13
0 6 3 6 9 0 0 4 2 8
4 4 6 6 7 2 4 3 6 1
3 6 6 6 1 6 4 6 6 1
4 2 6 4 1 0 0 0 6 6
2 2 2 4 1 2 2 4 2 1
0 6 2 4 5 2 4 4 4 4
4 2 4 4 3
3 3
2 5
6
6
9 10 4 7 5 6


=================
