2010-1094

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

by yuxingdubai

解题报告:
{{{
一道简单题, 就由我这个唯一没AC的人来写结题报告吧.. T_T
这道题就是让我们求折线段上(m+1)等分点的坐标.
数据范围和浮点误差都不用担心, 直接模拟就可以解出.
找点有两种循环, 一种是以线段为单位循环, 循环n次, 一次循环内找出该线段上所有的CP, 在下面给出的代码中就是采用这种循环方式;
另一种是从CP的方向考虑, 一次循环内找出一个CP的坐标.
只要注意好相邻CP之间会跨越多个折线段就可以了.
}}}

代码:
{{{
#!cpp
#include<cstdio>
#include<cmath>
using namespace std;
int x[1010], y[1010];
double e[1010];
double len(int x1, int y1, int x2, int y2){
    double dx = x2 - x1;
    double dy = y2 - y1;
    return sqrt(dx*dx+dy*dy);   
}
int main(){
    int n, m, t = 1;
    while(2 == scanf("%d%d", &n, &m)){
        double suml = 0, avl;
        x[0] = y[0] = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d%d", x+i, y+i);
            suml += e[i] = len(x[i-1], y[i-1], x[i], y[i]);
        }
        avl = suml / (m+1);
        printf("Route %d\n", t++);
        double cpx = 0, cpy = 0, togo = avl;
        int num = 0;
        for(int i = 1; i <= n && num < m; i++){
            double gone = 0;
            while(gone + togo <= e[i] && num < m){
                gone += togo;
                togo = avl;
                cpx = x[i-1] + (x[i]-x[i-1])*gone/e[i];
                cpy = y[i-1] + (y[i]-y[i-1])*gone/e[i];
                printf("CP%d: (%.3f, %.3f)\n", ++num, cpx, cpy);
            }
            togo -= e[i] - gone;
        }    
    }
    return 0;    
}
}}}

by yuxingdubai

解题报告:

一道简单题, 就由我这个唯一没AC的人来写结题报告吧.. T_T
这道题就是让我们求折线段上(m+1)等分点的坐标.
数据范围和浮点误差都不用担心, 直接模拟就可以解出.
找点有两种循环, 一种是以线段为单位循环, 循环n次, 一次循环内找出该线段上所有的CP, 在下面给出的代码中就是采用这种循环方式;
另一种是从CP的方向考虑, 一次循环内找出一个CP的坐标.
只要注意好相邻CP之间会跨越多个折线段就可以了.

代码:

#include<cstdio>
#include<cmath>
using namespace std;
int x[1010], y[1010];
double e[1010];
double len(int x1, int y1, int x2, int y2){
    double dx = x2 - x1;
    double dy = y2 - y1;
    return sqrt(dx*dx+dy*dy);   
}
int main(){
    int n, m, t = 1;
    while(2 == scanf("%d%d", &n, &m)){
        double suml = 0, avl;
        x[0] = y[0] = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d%d", x+i, y+i);
            suml += e[i] = len(x[i-1], y[i-1], x[i], y[i]);
        }
        avl = suml / (m+1);
        printf("Route %d\n", t++);
        double cpx = 0, cpy = 0, togo = avl;
        int num = 0;
        for(int i = 1; i <= n && num < m; i++){
            double gone = 0;
            while(gone + togo <= e[i] && num < m){
                gone += togo;
                togo = avl;
                cpx = x[i-1] + (x[i]-x[i-1])*gone/e[i];
                cpy = y[i-1] + (y[i]-y[i-1])*gone/e[i];
                printf("CP%d: (%.3f, %.3f)\n", ++num, cpx, cpy);
            }
            togo -= e[i] - gone;
        }    
    }
    return 0;    
}