题目描述
这里有一辆赛车比赛正在进行,赛场上一共有N辆车,分别称为个g1,g2......gn。赛道是一条无限长的直线。最初,gi位于距离起跑线前进ki的位置。比赛开始后,车辆gi将会以vi单位每秒的恒定速度行驶。在这个比赛过程中,如果一辆赛车曾经处于领跑位置的话(即没有其他的赛车跑在他的前面),这辆赛车最后就可以得奖,而且比赛过程中不用担心相撞的问题。现在给出所有赛车的起始位置和速度,你的任务就是算出那些赛车将会得奖。
输入输出格式
输入格式:
第一行有一个正整数N表示赛车的个数。接下来一行给出N个整数,按顺序给出N辆赛车的起始位置。再接下来一行给出N个整数,按顺序给出N辆赛车的恒定速度。
输出格式:
输出包括两行,第一行为获奖的赛车个数。第二行按从小到大的顺序输出获奖赛车的编号,编号之间用空格隔开,注意最后一个编号后面不要加空格。
输入输出样例
说明
对于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; }
#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;
}
没有帐号? 立即注册