csu 1549: Navigition Problem(几何,模拟)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了csu 1549: Navigition Problem(几何,模拟),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2904字,纯文字阅读大概需要5分钟。
内容图文
1549: Navigition Problem
Time Limit: 1 Sec Memory Limit: 256 MBSubmit: 305 Solved: 90
[Submit][Status][Web Board]
Description
Navigation
is a field of study that focuses on the process of monitoring and
controlling the movement of a craft or vehicle from one place to
another. The field of navigation includes four general categories: land
navigation, marine navigation, aeronautic navigation, and space
navigation. (From Wikipedia)
Recently, slowalker encountered a problem in the project development of
Navigition APP. In order to provide users with accurate navigation
service , the Navigation APP should re-initiate geographic location
after the user walked DIST meters. Well, here comes the problem. Given
the Road Information which could be abstracted as N segments in
two-dimensional space and the distance DIST, your task is to calculate
all the postion where the Navigition APP should re-initiate geographic
location.
Input
The input file contains multiple test cases.
For each test case,the first line contains an interger N and a real
number DIST. The following N+1 lines describe the road information.
You should proceed to the end of file.
Hint:
1 <= N <= 1000
0 < DIST < 10,000
Output
For each the case, your program will output all the positions where the Navigition APP should re-initiate geographic location. Output “No Such Points.” if there is no such postion.
Sample Input
2 0.50
0.00 0.00
1.00 0.00
1.00 1.00
Sample Output
0.50,0.00 1.00,0.00 1.00,0.50 1.00,1.00
题意:有 n 条首尾相连的线段 (第1条不和第 n条相连).从第一个点的起点开始每次沿着线段平移 d 个单位到达某一个点,把每次的坐标输出,如果所有线段之和都小于d,输出 "No Such Points."
题解:模拟这个过程,每次确定当前的点在哪条线段上,假设当前点在line[i] ,那么我们设当前点为 (x,y), 可以得到它与line[i]起点的距离,然后通过公式可以推出当前点的位置,记得讨论斜率不存在的
情况。
#include <stdio.h> #include <string.h> #include <iostream> #include <math.h> #include <algorithm> usingnamespace std; constint N = 1005; struct Point { double x,y; } p[N]; struct Line { Point a,b; } line[N]; double len[N]; double dis(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double sum[N]; int main() { int n; double d; while(scanf("%d%lf",&n,&d)!=EOF) { double SUM = 0; sum[0] = 0; for(int i=1; i<=n+1; i++) { scanf("%lf%lf",&p[i].x,&p[i].y); if(i>1) { len[i-1] = dis(p[i],p[i-1]); SUM+=len[i-1]; sum[i-1] = sum[i-2]+len[i-1]; } } if(SUM<d) { printf("No Such Points.\n"); continue; } double now = 0,k,x,y; for(int i=1; i<=n;) { if(now+d<=sum[i]) { double L = now+d - sum[i-1]; double x1 = p[i].x,y1 = p[i].y; double x2 = p[i+1].x,y2 = p[i+1].y; if(x1!=x2) { k = (y1-y2)/(x1-x2); if(x2<x1) { x = x1-sqrt((L*L)/(k*k+1)); y = k*(x-x1)+y1; } else { x = x1+sqrt((L*L)/(k*k+1)); y = k*(x-x1)+y1; } } else { x = x1; if(y2<y1) y = y1-L; else y = y1+L; } printf("%.2lf,%.2lf\n",x,y); now = now+d; } else { i++; } } } }
原文:http://www.cnblogs.com/liyinggang/p/5792894.html
内容总结
以上是互联网集市为您收集整理的csu 1549: Navigition Problem(几何,模拟)全部内容,希望文章能够帮你解决csu 1549: Navigition Problem(几何,模拟)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。