生活随笔
收集整理的这篇文章主要介绍了
nyoj878格点
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
格点
时间限制：
1000 ms | 内存限制：
65535 KB 难度：
3
描述
所谓的格点——就是平面坐标系中，纵横坐标均为整数的点。
现在问题来了，给你平面上不同的两个格点P1 = （x1,y1）和 P2 = （x2,y2）,依次输出在线段P1P2上所有格点的坐标。
输入第一行有一个整数n，表示n组测试数据
接下来的n行，每一行有四个整数，分别表示x1,y1,x2,y2;
-10^6 < x1,x2,y1,y2 < 10^6;
输出每组测试数据依次输出线段上每个格点的坐标，占单独一行，具体格式见输出样例。样例输入 2
0 0 3 3
1 11 5 3
样例输出 (0,0),(1,1),(2,2),(3,3)
(1,11),(2,9),(3,7),(4,5),(5,3) 要注意的地方：点的输出顺序，比如输入1 8 -1 2，应该输出(1,8),(0,5),(-1,2)
而不是(-1,2),(0,5),(1,8)
思路一，代码多，思路简单，time 88ms
思路二，代码少，思路比思路一难一点，time 48ms
思路一:
求出线段所在直线方程，将两点间的整数坐标代入检验，没有斜率和注意斜率为0时。
测试数据来一发
4
-9 -3 4 -10
0 0 0 0
-1 2 3 2
1 2 1 5
答案
(-9,-3),(4,-10)
(0,0)
(-1,2),(0,2),(1,2),(2,2),(3,2)
(1,2),(1,3),(1,4),(1,5)
Ac代码:
#include <stdio.h>//time 88ms
#include <math.h>
struct point{double x,y;
}A,B;
int main() {int i, j, x, y, t;double ty;scanf("%d", &t);while(t--) {scanf("%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y);printf("(%.lf,%.lf)", A.x, A.y);double k, b;k = (A.y-B.y) / (A.x-B.x);b = A.y - k*A.x;if(fabs(A.x - B.x) < 1e-6) {i = A.y+1;j = B.y;if(i <= j) {for(; i <= j; i++) printf(",(%.lf,%d)", A.x, i);}else {for(i = i-2; i >= j; i--) printf(",(%.lf,%d)", A.x, i);}} else if(fabs(k - 0) < 1e-6) {i = A.x+1;j = B.x;if(i <= j) {for(; i <= j; i++) printf(",(%d,%.lf)",i , A.y);} else {for(i = i-2; i >= j; i--) printf(",(%d,%.lf)",i , A.y);}} else {i = A.x+1;j = B.x;if(i <= j) {for(; i <= j; i++) {ty = k*i+b;if(ty > 0) ty += 0.5;else ty -= 0.5;y = ty;if(fabs((y-b)/k-i) < 1e-6) printf(",(%d,%d)",i , y);}} else {for(i = i-2; i >= j; i--) {ty = k*i+b;if(ty > 0) ty += 0.5;else ty -= 0.5;//这里要小心 y = ty;if(fabs((y-b)/k-i) < 1e-6) printf(",(%d,%d)",i , y);}}}printf("\n");}return 0;
}
思路2:
用个例子比较好说，比如0 0 3 3，x和y每隔1就是一个符合题意得点，而0 1 2 4就是x隔2，y隔3时有符合题意的点
AC代码:
#include <stdio.h>//time 48ms
#include <stdlib.h>
struct point{int x,y;
}A,B;
int gcd(int a, int b) {return a == 0 ? b : gcd(b%a, a);
}
int main() {int i, j, x, y, t, tx, ty, k, g;scanf("%d", &t);while(t--) {int fx = 1, fy = 1;scanf("%d%d%d%d", &A.x, &A.y, &B.x, &B.y);printf("(%d,%d)", A.x, A.y);x = B.x-A.x;y = B.y-A.y;g = gcd(abs(y),abs(x));ty = y/g;tx = x/g;i = A.x;j = B.x;k = A.y+ty;if(i < j) {for(i += tx; i <= j; i += tx, k += ty) printf(",(%d,%d)",i , k);} else if(i > j){for(i += tx; i >= j; i += tx, k += ty) printf(",(%d,%d)",i , k);} else {if(A.y < B.y)for(i = A.y+ty; i <= B.y; i += ty) printf(",(%d,%d)",A.x , i);else for(i = A.y+ty; i >= B.y; i += ty) printf(",(%d,%d)",A.x , i);}printf("\n");}return 0;
}
总结
以上是生活随笔为你收集整理的nyoj878格点的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
