2014
01-05

# Run

Since members of Wuhan University ACM Team are lack of exercise, they plan to participate in a ten-thousand-people Marathon. It is common that the athletes run very fast at first but slow down later on. Start from this moment, we can assume that everyone is moving forward in a constant speed. ACMers love algorithms, so they want to know not only the result but also who may be in the leading position. Now we know all athletes’ position and speed at a specific moment. The problem is, starting from this moment, how many athletes may be the leader. Please notice that there’s no leader if two or more athletes are at the leading position at the same time. No two athletes may have the same speed.

The input consists of several test cases. The first line of input consists of an integer T, indicating the number of test cases. The first line of each test case consists of an integer N, indicating the number of athletes. Each of the following N lines consists of two integers: p, v, indicating an athlete’s position and speed.

Technical Specification

1. T ≤ 20
2. 0 < N ≤ 50000
3. 0 < p, v ≤ 2000,000,000
4. An athlete’s position is the distant between him/her and the start line.
5. The Marathon is so long that you can assume there’s no finishline.

The input consists of several test cases. The first line of input consists of an integer T, indicating the number of test cases. The first line of each test case consists of an integer N, indicating the number of athletes. Each of the following N lines consists of two integers: p, v, indicating an athlete’s position and speed.

Technical Specification

1. T ≤ 20
2. 0 < N ≤ 50000
3. 0 < p, v ≤ 2000,000,000
4. An athlete’s position is the distant between him/her and the start line.
5. The Marathon is so long that you can assume there’s no finishline.

1
3
1 1
2 3
3 2

2

by—cxlove

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<ctime>
#define maxn 200005
#define eps 1e-8
#define inf 2000000000
#define LL long long
#define zero(a) fabs(a)<eps
#define MOD 19901014
#define N 1000005
#define pi acos(-1.0)
using namespace std;
int t,n;
double X,Y;
double best[50];
struct Point{
double x,y;
bool check(){
if(x>-eps&&x<eps+X&&y>-eps&&y<eps+Y)
return true;
return false;
}
}p[1005],tp[50];
double dist(Point p1,Point p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double slove(Point p0){
double ans=inf;
for(int i=0;i<n;i++)
ans=min(ans,dist(p[i],p0));
return ans;
}
int main(){
scanf("%d",&t);
srand(time(NULL));
while(t--){
scanf("%lf%lf%d",&X,&Y,&n);
for(int i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
for(int i=0;i<15;i++){
tp[i].x=(rand()%1000+1)/1000.0*X;
tp[i].y=(rand()%1000+1)/1000.0*Y;
best[i]=slove(tp[i]);
}
double step=max(X,Y)/sqrt(1.0*n);
while(step>1e-3){
for(int i=0;i<15;i++){
Point cur,pre=tp[i];
for(int j=0;j<35;j++){
double angle=(rand()%1000+1)/1000.0*2*pi;
cur.x=pre.x+cos(angle)*step;
cur.y=pre.y+sin(angle)*step;
if(!cur.check()) continue;
double tmp=slove(cur);
if(tmp>best[i]){
tp[i]=cur;
best[i]=tmp;
}
}
}
step*=0.85;
}
int idx=0;
double ans=0;
for(int i=0;i<15;i++){
if(best[i]>ans){
ans=best[i];
idx=i;
}
}
printf("The safest point is (%.1f, %.1f).\n",tp[idx].x,tp[idx].y);
}
return 0;
}

1. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;
{
degree[*j]++;
}
}

为什么每遍历一条链表，要首先将每个链表头的顶点的入度置为0呢？
比如顶点5，若在顶点1、2、3、4的链表中出现过顶点5，那么要增加顶点5的入度，但是在遍历顶点5的链表时，又将顶点5的入度置为0了，那之前的从顶点1234到顶点5的边不是都没了吗？

2. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！

3. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。