程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj3190【JLOI013】賽車

bzoj3190【JLOI013】賽車

編輯:關於C++

3190: [JLOI2013]賽車

Time Limit:10 SecMemory Limit:128 MB
Submit:1445Solved:454
[Submit][Status][Discuss]

Description

  這裡有一輛賽車比賽正在進行,賽場上一共有N輛車,分別稱為個g1,g2……gn。賽道是一條無限長的直線。最初,gi位於距離起跑線前進ki的位置。比賽開始後,車輛gi將會以vi單位每秒的恆定速度行駛。在這個比賽過程中,如果一輛賽車曾經處於領跑位置的話(即沒有其他的賽車跑在他的前面),這輛賽車最後就可以得獎,而且比賽過程中不用擔心相撞的問題。現在給出所有賽車的起始位置和速度,你的任務就是算出那些賽車將會得獎。  

Input

第一行有一個正整數N表示賽車的個數。 接下來一行給出N個整數,按順序給出N輛賽車的起始位置。 再接下來一行給出N個整數,按順序給出N輛賽車的恆定速度。  

Output

  輸出包括兩行,第一行為獲獎的賽車個數。 第二行按從小到大的順序輸出獲獎賽車的編號,編號之間用空格隔開,注意最後一個編號後面不要加空格。    

Sample Input

4
1 1 0 0
15 16 10 20

Sample Output

3
1 2 4

HINT

對於100%的數據N<=10000, 0<=ki<=10^9, 0<=vi<=10^9

2016.1.17新加數據一組 By Nano_ape

計算幾何,維護一個y軸右面的半平面交。

注意兩個賽車速度和起始狀態都相同的情況。

#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 10005
#define eps 1e-8
using namespace std;
int n,top,ans[maxn],f[maxn];
struct car{int p,v,id;}a[maxn],s[maxn];
vector v[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline bool cmp(car x,car y)
{
	return (x.v==y.v)?x.p>y.p:x.v=2&&cross(s[top],s[top-1])>cross(s[top-1],a[i])) top--;
		while (top>=1&&cross(s[top],a[i])<-eps) top--;
		s[++top]=a[i];
	}
	F(i,1,top) ans[i]=s[i].id;
	int tt=top;
	F(i,1,tt) for(int j=0;j
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved