poj 2674 Linear world 弹性碰撞升级的蚂蚁-白红宇

poj 2674 Linear world 弹性碰撞升级的蚂蚁

阅读量：4112 次

发布时间：2019-05-25

本文共 5138 字，大约阅读时间需要 17 分钟。

Linear world

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 3078		Accepted: 680

Description

The Disc, being flat, has no real horizon. Any adventurous sailors who get funny ideas from staring at eggs and oranges for too long and set out for the antipodes soon learned that the reason why distant ships sometimes looked as though they were disappearing over the edge of the world was that they were disappearing over the edge of the world. (Terry Pratchett -Colour of Magic)

Not so long time ago people used to believe that they live on 2-D world and if they will travel long enough in one direction, they will fall down over the edge. Even when it was proved that the Earth is rounded some of them were still afraid to travel to the southern hemisphere.

Try to imagine one 1-D (linear) world. On such world there are only two possible directions (left and right). All inhabitants of such world were created exactly at the same time and suddenly all of them start to move (all with same constant velocity) in one or the other direction. If two inhabitants encounter each other, they politely exchange greetings and then they turn around and start to move in an opposite direction. When an inhabitant reaches the end of the world he falls away and disappears.

Your task is to determine, for a given scenario of creation, which inhabitant and when (counting from the moment of creation) will be the last one to fall away. You can assume that the time required to exchange greetings and turn around is 0.

Input

The input consists of multiple descriptions (data sets) of the creation moment. File structure is as follows:

DIR POS NAME

...

The first line defines the number of inhabitants (N<32000). Data set starting with value N=0 represents the end of the input file. The second line contains length of the world L(float) and velocity of inhabitants V(float). Both values are always positive. In next N lines the data about inhabitants are given in an order of increasing POS (positive direction):

DIR – initial direction ('p' or 'P' for positive and 'n' or 'N' for negative)

POS – position in the time of creation (0<=POS<=L)

NAME – name of inhabitant (string up to 250 characters)

Input values within one line are separated with at least one space and there will be no empty lines in input. You may assume that input is always correct and that each data set has only one unique solution.

Output

The output consists of one line per each input data set. The first value should be the time when the last inhabitant will fall of the linear world counting from the moment of creation. Value should be printed truncated to two decimal places in a field 13 characters wide. The second value should be the name of the inhabitant. Values should be separated with single space character.

Sample Input

1   13.5 2   p 3.5 Smarty  4  10  1  p  1  Helga  n 3 Joanna  p  5  Venus  n  7  Clever  0

Sample Output

5.00 Smarty         9.00 Venus

Source

题意：给你n个人的初始位置（x轴上）和名字，以及运动的方向，已知运动的速度均是v,

和一个闭区间的长度，求最后离开这个区间的人的时间和姓名；

错因：这道题最长的时间很容易分析出来，难就难在名字怎么输出，，我刚刚想的是最后离开的人

一定是刚开始最中间的两个，但是具体是哪一个就想不出来了，，；

分析：与前面那道球的碰撞问题类似，先假设不碰撞求得各个球的位置，然后再排下序得到相应的

位置得到的各个球

，因为相对位置不变！！！！

易错点：

需要特别注意的是；本题要求是截取两位小数输出，直接用%f输出t会wa，因为%f是四舍五入

而不是截取；还有注意看清题目要求是大小写；还要注意double用%lf输入，%f输出

#include
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              #include 
              
                #include 
               
                 using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long LL; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; int n;double len, v; struct Node{ double p,l; char name[300]; char d[3]; int id; }node[32005]; bool cmp(Node a, Node b) { return a.p 
                
                 maxn) maxn=node[i].l; node[i].id=i; } double t=maxn/v;int j,minn=inf; delay(t); sort(node+1,node+n+1,cmp); for(int i=1;i<=n;i++) { double x1=abs(node[i].p-len); double x2=abs(node[i].p); if(x1
                 
                  
                   x2?x2:x1; } }/最后离开的人 for(int i=1;i<=n;i++) if(node[i].id==j) { printf("%13.2f %s\n",(int(t*100))/100.0, node[i].name); break; } } return 0; }

下面是第一次wa的代码：

#include
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include
             #include 
             
               #include 
              
                using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long LL; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; int n;double len, v; struct Node{ double p,l; char name[300]; char d[3]; }node[32005]; bool cmp(Node a, Node b) { return a.l > b.l; } void delay(int t) { for(int i=1;i<=n;i++) { if(node[i].d[0]=='p') node[i].p+=v*t; else node[i].p-=v*t; } } int main() { while (~scanf("%d", &n)&&n) { double maxn=0; scanf("%lf %lf", &len, &v); for (int i = 1; i <= n; i++) { scanf("%s %lf %s", node[i].d, &node[i].p, node[i].name); if (node[i].d[0] == 'p') node[i].l = len - node[i].l; if(node[i].l>maxn) maxn=node[i].l; } double t=(maxn+v-1)/v;int j,minn=inf; sort(node+1,node+n+1,cmp); for(int i=1;i<=n;i++) if(abs(node[i].p-len)

转载地址：http://bvgsi.baihongyu.com/

你可能感兴趣的文章