WC2010 能量场

题目:

  物理学家栋栋最近在研究一个能量场。在这个能量场中有个粒子,每个粒子都有两个属性:质量和结合系数
  栋栋发现,在这个能量场中,每个粒子都有两极,N极和S极。两个粒子相遇时,符合“同极相斥,异极相吸”的原则,只能是一个粒子的N极和另一个粒子的S极连接到一起。当质量为,结合系数为的粒子a的N极与另一个质量为,结合系数为的粒子b的S极直接连接时,可以产生大小为的结合能量。
  请解决以下两个问题:
  1.在能量场的个粒子中哪两个粒子直接连接的能量最大。
  2.从中找出任意k个粒子排列成一个环,相邻两个粒子分别合并,使得总能量最大,产生负能量的粒子必须是环上连续的一段。
  栋栋发明了一种方法,能选择其中的任意个粒子,将的N极与的S极连接的N极与的S极连接, 其中两两不同。可以在中任意取值,如使用栋栋的这种方法连接,选择哪些粒子可以得到最大的能量

思路:

  对于第一问, 转化一下就可以变成斜率式,因为 坐标不单调,所以要用分治来转移。
  而对于第二问,因为斜率优化解决的是比较两次转移哪个更优,这和第二问要求的东西好像就没什么关联了。所以要从另一个角度分析 ,拆开变成 ,就可以看成 的叉积。那就可以利用叉积的几何意义,往图形的面积上想,因为题目要求负的代价是连续的,所以一个环的能量就是一个平面图形的面积(如果负值不连续形成的是多个图形的面和,可能还有一些奇怪的图形?),那最大值就是这个点集的凸包面积。
  ps:好像第二问叉积的模型也可用于第一个问,大概是求一个最大的三角形。

代码:

#include <bits/stdc++.h>
#define debug(x) cerr << "DEBUG: " << #x << '=' << x << endl
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const db eps = 1e-8;

const int N = 5e4 + 5;

db m[N], c[N];
int n;

bool cmp_m(int x, int y) {
    return m[x] > m[y];
}
bool cmp_c(int x, int y) {
    return c[x] < c[y];
}
db calc(int a, int b) {
    return m[a] * m[b] * (c[a] - c[b]);
}

namespace Part1 {
    int que[N], hed, tai;
    db y(int i) {return c[i] * m[i];}
    db x(int i) {return m[i];}
    struct Data {
        db x, y;
        int id;
        bool operator< (const Data d) const {
            if(x == d.x) return y < d.y;
            return x < d.x;
        }
    } d[N], tmp[N];
    bool check(int i, int j, int k) {
        return (y(i) - y(j)) * (x(j) - x(k)) >= (y(j) - y(k)) * (x(i) - x(j));
    }
    db ans = -1.0 / 0.0;
    int a, b, id[N];
    void cdq(int l, int r) {
        if(l == r) {d[l] = (Data) {x(id[l]), y(id[l]), id[l]}; return;}
        int mid = (l + r >> 1);
        cdq(l, mid);
        int hed = 1, tai = 0;
        rep(i, l, mid) {
            while(hed < tai && check(que[tai - 1], que[tai], d[i].id)) tai--;
            que[++tai] = d[i].id;
        }
        rep(i, mid + 1, r) {
            int o = id[i];
            while(hed < tai && calc(o, que[hed]) < calc(o, que[hed + 1])) hed++;
            if(tomax(ans, calc(o, que[hed]))) a = o, b = que[hed];
        }
        cdq(mid + 1, r);
        int i = l, j = mid + 1, p = l;
        while(i <= mid && j <= r) {
            if(d[i] < d[j]) tmp[p++] = d[i++];
            else tmp[p++] = d[j++];
        }
        while(i <= mid) tmp[p++] = d[i++];
        while(j <= r) tmp[p++] = d[j++];
        rep(i, l, r) d[i] = tmp[i];
    }
    void solve() {
        rep(i, 1, n) id[i] = i;
        sort(id + 1, id + 1 + n, cmp_c);
        cdq(1, n);
        printf("%d %d\n", a, b);
    }
}

namespace Part2 {
    int operatorOP;
    struct Point {
        db x, y;
        int id;
        bool operator< (const Point p) const {
            if(x == p.x) return (y < p.y) == operatorOP;
            return x < p.x;
        }
        bool operator== (const Point p) const {
            return id == p.id;
        }
    } p[N], up[N], down[N], vec[N];
    bool check(Point a, Point b, Point c) {
        return (a.y - b.y) * (b.x - c.x) >= (b.y - c.y) * (a.x - b.x);
    }
    void solve() {
        rep(i, 1, n) p[i] = (Point) {m[i], m[i] * c[i], i};
        operatorOP = 1; sort(p + 1, p + 1 + n);
        int hed = 1, tai = 0, tot1, tot2;
        rep(i, 1, n) {
            while(hed < tai && check(up[tai - 1], up[tai], p[i])) tai--;
            up[++tai] = p[i];
        }
        tot1 = tai;
        operatorOP = 0; sort(p + 1, p + 1 + n);
        hed = 1; tai = 0;
        rep(i, 1, n) {
            while(hed < tai && check(p[i], down[tai], down[tai - 1])) tai--;
            down[++tai] = p[i];
        }
        tot2 = tai;
        int tot = 0;
        rep(i, 1, tot1) vec[++tot] = up[i];
        if(vec[tot] == down[tot2]) tot--;
        drep(i, tot2, 1) vec[++tot] = down[i];
        if(vec[tot] == vec[1]) tot--;
        printf("%d\n", tot);
        drep(i, tot, 1) printf("%d%c", vec[i].id, " \n"[i == 1]);
    }
}

int main() {
    File(efield);
    scanf("%d", &n);
    rep(i, 1, n) scanf("%lf%lf", &m[i], &c[i]);
    Part1::solve();
    Part2::solve();
    return 0;
}