Rockdu's Blog

题目描述

这里有一辆赛车比赛正在进行，赛场上一共有N辆车，分别称为个g1，g2......gn。赛道是一条无限长的直线。最初，gi位于距离起跑线前进ki的位置。比赛开始后，车辆gi将会以vi单位每秒的恒定速度行驶。在这个比赛过程中，如果一辆赛车曾经处于领跑位置的话（即没有其他的赛车跑在他的前面），这辆赛车最后就可以得奖，而且比赛过程中不用担心相撞的问题。现在给出所有赛车的起始位置和速度，你的任务就是算出那些赛车将会得奖。

输入输出格式

输入格式：

第一行有一个正整数N表示赛车的个数。接下来一行给出N个整数，按顺序给出N辆赛车的起始位置。再接下来一行给出N个整数，按顺序给出N辆赛车的恒定速度。

输出格式：

输出包括两行，第一行为获奖的赛车个数。第二行按从小到大的顺序输出获奖赛车的编号，编号之间用空格隔开，注意最后一个编号后面不要加空格。

输入输出样例

4
1 1 0 0
15 16 10 20

3
1 2 4

说明

对于100%的数据N<=10000, 0<=ki<=10^9, 0<=vi<=10^9

2016.1.17新加数据一组 By Nano_ape

简单的板子题，做半平面交然后找出所有在答案凸包上的直线就可以了。

才发现自己以前的半平面交板子是假的。半平面交一定要在斜率相等的半平面中选一个最优的出来去重才行。然后还要在上下左右框4个无限远的框框。

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 1e5 + 5;
const double x0 = -2002;
const double x1 = 423;
int vis[maxn], ord[maxn];

namespace G2D {
    #define T long double
    #define eps 1e-18
    struct P {T x, y;P(T _x, T _y):x(_x), y(_y){}P(){}};
    inline int sg(T a) {return (a > -eps) - (a < eps);}
    bool cmp_x(const P &A, const P &B) {return A.x == B.x ? A.y < B.y : A.x < B.x;}
    inline P operator +(const P &A, const P &B) {return P(A.x + B.x, A.y + B.y);}
    inline P operator -(const P &A, const P &B) {return P(A.x - B.x, A.y - B.y);}
    inline P operator -(const P &A) {return P(-A.x, -A.y);}
    inline T operator *(const P &A, const P &B) {return A.x * B.y - B.x * A.y;}
    inline P operator *(const T &A, const P &B) {return P(A * B.x, A * B.y);}
    inline int AOnLeft(const P &A, const P &B) {return sg(B * A);} /*不要乘反，右手定则*/
    inline int AOnLeft(const P &A, const P &s, const P &t) 
        {return sg((t - s) * (A - s));} /*不要乘反，右手定则*/
    inline T Gdis(const P &A, const P &B) {return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));}
    struct Line {
        P s, t; int id; T a;Line(){}
        Line(P _s, P _t):s(_s), t(_t){a = atan2((_t - _s).x, (_t - _s).y);}
    }q[maxn << 1];
    inline bool operator <(const Line &A, const Line &B) 
        {return A.a < B.a;}
    inline P Itsec(const Line &A, const Line &B) {
        T s1 = ((B.t - A.s) * (B.s - A.s)), s2 = ((B.s - A.t) * (B.t - A.t));
        return (s1 / (s1 + s2)) * (A.t - A.s) + A.s;
    }
    int icnt = 0;
    Line l[maxn];
    int HPI(Line * lset, int size) {
        int L = 1, R = 0, ret = 0, tot = 0;
        l[tot].a = 66666.0;
        sort(lset + 1, lset + size + 1);
        for(register int i = 2; i <= size; ++i) {
        	if(sg(lset[i].s.y - lset[i - 1].s.y) == 0) ord[lset[i].id] = icnt;
        	else ord[lset[i].id] = ++icnt;
        }
        for(register int i = 1; i <= size; ++i) {
        	//l[++tot] = lset[i];
        	if(sg(lset[i].a - l[tot].a) != 0) 
                l[++tot] = lset[i], l[tot].id = ord[lset[i].id];
        	else {
                if(AOnLeft(lset[i].s, l[tot].s, l[tot].t) > 0)
            		l[tot] = lset[i], l[tot].id = ord[lset[i].id];
            }
        }
        
        if(tot >= 1) q[++R] = l[1];
        if(tot >= 2) q[++R] = l[2];
        if(tot > 2) {
            for(register int i = 3; i <= tot; ++i) {
                while(L < R && AOnLeft(Itsec(q[R], q[R - 1]), l[i].s, l[i].t) < 0) --R;
                while(L < R && AOnLeft(Itsec(q[L], q[L + 1]), l[i].s, l[i].t) < 0) ++L;
                q[++R] = l[i];
            }
            while(L < R && AOnLeft(Itsec(q[R], q[R - 1]), q[L].s, q[L].t) < 0) --R;
            while(L < R && AOnLeft(Itsec(q[L], q[L + 1]), q[R].s, q[R].t) < 0) ++L;
            //if(R - L <= 1) return 0;
        }
        for(register int i = L; i <= R; ++i)
        	vis[q[i].id] = 1, ret += q[i].id > 0;
        return ret;
    }
}
 
using namespace G2D;
Line ls[maxn];
int k, c, n, cnt, d1[maxn], d2[maxn];
int ans[maxn], acnt;
 
int main() {
    //freopen("race1.in", "r", stdin);
    //freopen("race1.out", "w", stdout);
   	scanf("%d", &n);
    for(register int i = 1; i <= n; ++i)
    	scanf("%d", &d1[i]);
    for(register int i = 1; i <= n; ++i)
    	scanf("%d", &d2[i]);
    for(register int i = 1; i <= n; ++i) {
        k = d2[i], c = d1[i];
        ls[++cnt] = Line(P(x0, c + x0 * k),
                        P(x1, c + x1 * k));
        ls[cnt].id = i;
    }
    ls[++cnt] = Line(P(0, 0), P(0, -1e5));
    ls[cnt].id = 0;
    ls[++cnt] = Line(P(0, 0), P(1e5, 0));
    ls[cnt].id = 0;
    HPI(ls, cnt);
    int ret = 0;
    for(register int i = 1; i <= n; ++i)
    	if(vis[ord[i]]) ++ret;
    printf("%d\n", ret);
    for(register int i = 1; i <= n; ++i)
    	if(vis[ord[i]]) printf("%d ", i);
    return 0;
}