随笔-19  评论-1  文章-0  trackbacks-0
把在n条线段中(以(0,0)为起点)放入m个点,使其等分为m+1份。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3414
#include<stdio.h>
#include
<math.h>
struct point{
    
double x,y,len;
}
p[1002];
int main()
{
    
int n,m,i,j,ca=1;
    
double ave,len,ax,ay;
    
while(scanf("%d%d",&n,&m)!=EOF)
    
{
        p[
0].x=0; p[0].y=0; ave=0;
        
for(i=1;i<=n;i++){
            scanf(
"%lf%lf",&p[i].x,&p[i].y);
            p[i].len
=sqrt((p[i].x-p[i-1].x)*(p[i].x-p[i-1].x)+(p[i].y-p[i-1].y)*(p[i].y-p[i-1].y));
            
//printf("%.3f %.3f %.3f\n",p[i].x,p[i].y,p[i].len);
            ave+=p[i].len;
        }

        ave
/=(m+1); //每一份的均长
        j=0;  //沿着线段走
       
// printf("%.3f\n",ave);
        printf("Route %d\n",ca++);
        
for(i=1;i<=m;i++)
        
{
            len
=0;
            
for(; j<n;j++)
            
{
                
if(len+p[j+1].len>ave)
                    
break;
                len
+=p[j+1].len;
            }

            
double res=ave-len;
            
//printf("%d %.3f\n",j,res);
            ax=p[j].x+(res/p[j+1].len)*(p[j+1].x-p[j].x);
            ay
=p[j].y+(res/p[j+1].len)*(p[j+1].y-p[j].y);
            printf(
"CP%d: (%.3lf, %.3lf)\n",i,ax,ay);
            p[j].x
=ax; p[j].y=ay;
            p[j
+1].len=sqrt((p[j+1].x-p[j].x)*(p[j+1].x-p[j].x)+(p[j+1].y-p[j].y)*(p[j+1].y-p[j].y));
        }

    }

    
return 0;
}
posted on 2010-10-07 18:25 孟起 阅读(347) 评论(0)  编辑 收藏 引用 所属分类: 计算几何

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理