首页 > ACM题库 > HDU-杭电 > HDU 4077-Slalom[解题报告]HOJ
2015
04-16

HDU 4077-Slalom[解题报告]HOJ

Slalom

问题描述 :

Haunted Graveyard
In spite of the scarcity of snowfall in Madrid, interest in winter sports is growing in the city, especially with regard to skiing. Many people spend several weekends or even full weeks improving their skills in the mountains.In this problem we deal with only one of the multiple alpine skiing disciplines: slalom. A course is constructed by laying out a series of gates, which are formed by two poles. The skier must pass between the two poles forming each gate. The winner is the skier who takes the least time to complete the course while not missing any of the gates.You have recently started to learn to ski, but you have already set yourself the goal of taking part in the Winter Olympic Games of 2018, for which Madrid will presumably present a candidature. As part of the theoretical training, you need to write a program that calculates, given a starting point and a series of gates, the minimum-length path starting from the point given and passing through each gate until you reach the last one, which is the finish line. You may assume that the gates are horizontal and are ordered from highest to lowest, so that you need to pass through them in order. You consider yourself an accomplished skier, so you can make any series of turns, no matter how difficult, and your only concern is minimizing the total length of the path.

输入:

The fi rst line of each case gives the number of gates n (1 <= n <= 1 000). The next line contains two floating point numbers, the Cartesian coordinates x and y of the starting position, in that order. Next come n lines with three floating point numbers each, y x1 x2, meaning that the next gate is a horizontal line from (x1; y) to (x2; y). You can safely assume that x1 < x2. The values of y are strictly decreasing and are always smaller than that of the starting position. The last gate represents the nish line. All coordinates are between -500 000 and 500 000, inclusive. A value of 0 for n means the end of the input. A blank line follows each case.

输出:

The fi rst line of each case gives the number of gates n (1 <= n <= 1 000). The next line contains two floating point numbers, the Cartesian coordinates x and y of the starting position, in that order. Next come n lines with three floating point numbers each, y x1 x2, meaning that the next gate is a horizontal line from (x1; y) to (x2; y). You can safely assume that x1 < x2. The values of y are strictly decreasing and are always smaller than that of the starting position. The last gate represents the nish line. All coordinates are between -500 000 and 500 000, inclusive. A value of 0 for n means the end of the input. A blank line follows each case.

样例输入:

2
0 2
1 1 2
0 0.5 3
3
0 4
3 1 2
2 -1 0
1 1 2
0

样例输出:

2.41421356237
4.24264068712


Dave
Time
Limit: 2000/1000 MS
(Java/Others)    Memory
Limit: 65768/65768 K (Java/Others)
Total Submission(s):
1512    Accepted
Submission(s): 494
Problem Description
Recently, Dave is boring, so he often walks around. He finds that
some places are too crowded, for example, the ground. He couldn’t
help to think of the disasters happening recently. Crowded place is
not safe. He knows there are N
(1<=N<=1000) people on the ground.
Now he wants to know how many people will be in a square with the
length of R (1<=R<=1000000000).
(Including boundary).
Input
The input contains several cases. For each case there are two
positive integers N and R, and then N lines follow. Each gives the
(x, y) (1<=x, y<=1000000000)
coordinates of people. 
Output
Output the largest number of people in a square with the length of
R.
Sample Input
3 2 1
1 2 2 3 3
Sample Output
3
Hint
If two people stand in one place, they are embracing.
Source
The 36th ACM/ICPC Asia Regional Dalian Site —— Online
Contest
Recommend
lcy
简单题,不多说了
code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define le 1002
typedef struct{
int x,y;
}re;
re ar[le];
int xx[le] , yy[le];
int n , R;
int max(int va,int vb){
return va > vb ? va : vb;
}
void input(){
int i,j;
for (i = 0 ; i < n ; i++){
scanf (“%d%d”,&ar[i].x ,
&ar[i].y);
yy[i] = ar[i].y;
}
}
int judge(){
int i , j , mx = 0 , sum , k , up , left;
sort(yy , yy + n);
for (i = 0 ; i < n ; i++){
up = yy[i] + R;
k = 0;
for (j = 0 ; j < n ; j++){
if (ar[j].y >= yy[i]
&& ar[j].y <=
up)
xx[k++] = ar[j].x;
}
sort(xx , xx + k);
left = 0;
sum = 1;
for (j = 1 ; j < k ; j++){
if(xx[left] + R >= xx[j])
sum++;
else {
mx = max(sum , mx);
while (xx[left] + R < xx[j]){
sum–;
left++;
}
sum++;
}
}
mx = max(sum , mx);
}
return mx;
}
void deal(){
int ans = judge();
printf(“%d\n”,ans);
}
int main(void){
while(scanf(“%d%d”,&n , &R) ==
2){
input();
deal();
}
return 0;
}
参考:http://blog.sina.com.cn/s/blog_64018c250100u586.html


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法