题目链接&＃xff1a;http://codeforces.com/problemset/problem/404/B
题目意思&＃xff1a;Valera 参加马拉松&＃xff0c;马拉松的跑道是一个边长为a的正方形&＃xff0c;要求Valera从起点(0&＃xff0c;0&＃xff09;出发&＃xff0c;每经过距离d就给他一杯drink。求出n个位置&＃xff0c;即Valera每经过d距离的position。
一开始我是直接模拟的&＃xff0c;每次算出一个position就记录离该边最末还剩多少距离&＃xff0c;假设为k&＃xff0c;然后更新初始已有的距离k&＃xff0c;又开始加a的距离直到到达下一个点...代码复杂之余&＃xff0c;还超时了。
比较好的作法是&＃xff1a;既然要求position&＃xff0c;那么这个position一定是经过 i*d&＃xff08;i &＃61; 1 ~ n&＃xff09; 的距离的。那么问题关键就是定位&＃xff01;也就是坐标位置&＃xff01;这时需要知道Valera 经过多少条长度为a的边i*d/a &＃xff08;k&＃xff09;。接着就是确定具体是那条边了&＃xff0c;可以通过对 k mod 4来求得。下边&＃xff1a;0 &＃xff1b;右边&＃xff1a;1&＃xff1b; 上边&＃xff1a;2&＃xff1b; 左边&＃xff1a;3。另外引入t&＃xff0c;它表示经过id距离之后&＃xff0c;与经过相应的a边的长度之差&＃xff0c;即t &＃61; id - ka。
至于具体的坐标点则根据这些边的不同而有所不同。由于一直是逆时针跑的&＃xff0c;因此下边的x坐标是&＃xff08;t&＃xff0c;0)&＃xff0c;右边是(a, t)&＃xff0c; 上边是&＃xff08;a-t, a&＃xff09;&＃xff08;求的时候是逆时针方向的&＃xff0c;也就是该点离右边的距离&＃xff0c;我们需要求的是离左边的距离&＃xff09;&＃xff0c;左边&＃xff08;0&＃xff0c; a-t&＃xff09;&＃xff08;与上边同理&＃xff09;
还有一个要注意的地方&＃xff0c;就是要取 int64了&＃xff0c;10^5 * 10^5 &＃xff01;
1 #include
2 #include
3 #include
4 using namespace std;
5
6 int main()
7 {
8 double a, d, t;
9 __int64 k, n, i;
10 while (scanf("%lf%lf%I64d", &a, &d, &n) !&＃61; EOF)
11 {
12 double zero &＃61; 0.0;
13 for (i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)
14 {
15 k &＃61; i * d / a;
16 t &＃61; i * d - k * a;
17 // printf("k &＃61; %d, t &＃61; %lf\n", k, t);
18 if (k % 4 &＃61;&＃61; 0)
19 printf("%lf %lf\n", t, zero);
20 else if (k % 4 &＃61;&＃61; 1)
21 printf("%lf %lf\n", a, t);
22 else if (k % 4 &＃61;&＃61; 2)
23 printf("%lf %lf\n", a-t, a);
24 else
25 printf("%lf %lf\n", zero, a-t);
26 }
27 }
28 return 0;
29 }
京公网安备 11010802041100号