求bug…蚂蚁爬过的整点
求Bug。。。蚂蚁爬过的整点
Time Limit:1000MS Memory Limit:65535K
题型: 编程题 语言: 无限制
描述
一蚂蚁在地图上爬过，小明在地图上建个坐标，将蚂蚁留下的痕迹分成多条线段首位相连而成，
且那些线段的端点都是整数点，现在他想知道这只蚂蚁经过了坐标中多少个整数点。
输入格式
第一行输入一个整数t，表示case数；对于每个case，第一行输入一个整数n(0<=n<=10)，代表蚂蚁经过的线段的数量，
接下来n+1行，每行有两个整数x，y(-10000<=x,y<=10000)，表示蚂蚁依次经过线段的端点。
输出格式
每个case输出一行，蚂蚁所经过的整数点数量。
输入样例
1
3
0 0
0 4
2 2
2 0
输出样例
9
我的代码是错误，但是我找不到错误输入。。。
试过级组数据，木有办法。。。交了几次都是错误。。。
- C/C++ code
#include <stdio.h>#include <stdlib.h>typedef struct{ int x,y;}POINT;//#define DEBUG#ifdef DEBUG#define MAX_CNT 100#else#define MAX_CNT 10000#endif //这是端点数组POINT g_Point[MAX_CNT];//这里记录经过的整点的坐标//因为最多10组数据，每组最多10000*2+1 = 20001，乘上10 = 200010 < 210000POINT g_PointOK[21*MAX_CNT];int g_iPointOKCnt = 0;inline int Min(int a,int b){ return a>b?b:a;}inline int Max(int a,int b){ return a>b?a:b;}int PointCmp(const void *a,const void *b){//排序用，相同返回0 const POINT *pa,*pb; pa = (const POINT *)a; pb = (const POINT *)b; if (pa->x != pb->x) { return pa->x - pb->x; } return pa->y - pb->y;}int GetPointCnt(POINT PointA,POINT PointB){ //计算 PointA 到 PointB 中有多少个整数点 int iRet = 0; //△x,△y, int dx = abs(PointA.x-PointB.x); int dy = abs(PointA.y-PointB.y); int i = 0; //横坐标相同 if (PointA.x == PointB.x) { POINT tmp; tmp.x = PointA.x; for (i = 0;i < dy + 1;i++) { //找到整点，存进记录数组 tmp.y = i+Min(PointA.y,PointB.y); g_PointOK[g_iPointOKCnt++] = tmp; } return dy + 1; } //start为左边点 POINT Start,End; if (PointA.x < PointB.x) { Start = PointA; End = PointB; } else { Start = PointB; End = PointA; } //tdx tdy是整点距始点的距离（带符号） int tdx = 0; int tdy = 0; for (i = Start.x+1 ; i<=End.x ; i++) { tdx = i - Start.x; tdy = tdx * (End.y - Start.y) / dx; if (tdx*dy%dx == 0) { //找到第一个整点 break; } } //这条线段整点个数 iRet = dx / tdx + 1; //把所有整点存进记录数组 POINT tmp; for (i = 0;i < iRet;i++) { tmp.x = Start.x + i*tdx; tmp.y = Start.y + i*tdy; g_PointOK[g_iPointOKCnt++] = tmp; } return iRet;}int main(){ int iCase = 0,i = 0,j = 0; int iLineCnt = 0; int iPointCnt = 0; scanf("%d",&iCase); while (iCase-- >0) { iPointCnt = 1; g_iPointOKCnt = 0; scanf("%d",&iLineCnt); for (i = 0;i <= iLineCnt;i++) { scanf("%d%d",&g_Point[i].x,&g_Point[i].y); if (i >= 1) { GetPointCnt(g_Point[i-1],g_Point[i]); } } //先排序，然后看有多少个不同的 qsort(g_PointOK,g_iPointOKCnt,sizeof(POINT),PointCmp); for (i = 1;i < g_iPointOKCnt;i++) { if (PointCmp(&g_PointOK[i-1],&g_PointOK[i]) != 0) { iPointCnt++; } } printf("%d\n",iPointCnt); } return 0;}[解决办法]
能给外网OJ地址吗？
粗看你的题目和你的代码，边界问题：
- C/C++ code
#define MAX_CNT 10000//接下来n+1行，每行有两个整数x，y(-10000<=x,y<=10000)，表示蚂蚁依次经过线段的端点//至少10000+吧。
[解决办法]
- C/C++ code
#include <stdio.h>#include <stdlib.h>typedef struct{ int x,y;}POINT;//#define DEBUG#ifdef DEBUG#define MAX_CNT 100#else#define MAX_CNT 10002#endif //这是端点数组POINT g_Point[MAX_CNT];//这里记录经过的整点的坐标//因为最多10组数据，每组最多10000*2+1 = 20001，乘上10 = 200010 < 210000POINT g_PointOK[21*MAX_CNT];int g_iPointOKCnt = 0;int Min(int a,int b){ return a>b?b:a;}int Max(int a,int b){ return a>b?a:b;}int PointCmp(const void *a,const void *b){//排序用，相同返回0 const POINT *pa,*pb; pa = (const POINT *)a; pb = (const POINT *)b; if (pa->x != pb->x) { return pa->x - pb->x; } return pa->y - pb->y;}void GetPointCnt(POINT PointA,POINT PointB){ //计算 PointA 到 PointB 中有多少个整数点 int iRet = 0; //△x,△y, int dx = abs(PointA.x-PointB.x); int dy = abs(PointA.y-PointB.y); int i = 0, px, py; if (dy != 0 && dx != 0) { if (dx > dy) { for ( i = min(PointA.y, PointB.y); i <= max(PointA.y, PointB.y); i++) { if ( 0 == (dx * abs(i-PointA.y)) % dy ) { px = ((dx * abs(i-PointA.y)) / dy) + PointA.x; if (px >= min(PointA.x, PointB.x) && px <= max(PointA.x, PointB.x)) { //TODO :(px, i) g_PointOK[g_iPointOKCnt].x = px; g_PointOK[g_iPointOKCnt++].y = i; } else { px = -((dx * abs(i-PointA.y)) / dy) + PointA.x; if (px >= min(PointA.x, PointB.x) && px <= max(PointA.x, PointB.x)) { //TODO :(px, i) g_PointOK[g_iPointOKCnt].x = px; g_PointOK[g_iPointOKCnt++].y = i; } else { //TODO :WARNG? } } } } } else { for ( i = min(PointA.x, PointB.x); i <= max(PointA.x, PointB.x); i++) { if ( 0 == (dy * abs(i-PointA.x)) % dx ) { py = ((dy * abs(i-PointA.x)) / dx) + PointA.y; if (py >= min(PointA.y, PointB.y) && py <= max(PointA.y, PointB.y)) { //TODO : (i, py) g_PointOK[g_iPointOKCnt].x = i; g_PointOK[g_iPointOKCnt++].y = py; } else { py = -((dy * abs(i-PointA.x)) / dx) + PointA.y; if (py >= min(PointA.y, PointB.y) && py <= max(PointA.y, PointB.y)) { //TODO : (i, py) g_PointOK[g_iPointOKCnt].x = i; g_PointOK[g_iPointOKCnt++].y = py; } else { //TODO :WARNG? } } } } } } else { if (dy != 0 && dx == 0) { //TODO : dy + 1 for ( i = min(PointA.y, PointB.y); i <= max(PointA.y, PointB.y); i++) { g_PointOK[g_iPointOKCnt].x = PointA.x; g_PointOK[g_iPointOKCnt++].y = i; } } else if (dy == 0 && dx != 0) { //TODO : dx + 1 for ( i = min(PointA.x, PointB.x); i <= max(PointA.x, PointB.x); i++) { g_PointOK[g_iPointOKCnt].x = i; g_PointOK[g_iPointOKCnt++].y = PointA.y; } } else { //TODO : 1 g_PointOK[g_iPointOKCnt].x = PointA.x; g_PointOK[g_iPointOKCnt++].y = PointA.y; } }}int main(){ int iCase = 0,i = 0,j = 0; int iLineCnt = 0; int iPointCnt = 0; scanf("%d",&iCase); while (iCase-- >0) { iPointCnt = 1; g_iPointOKCnt = 0; scanf("%d",&iLineCnt); for (i = 0; i <= iLineCnt; i++) { scanf("%d%d",&g_Point[i].x, &g_Point[i].y); if (i >= 1) { GetPointCnt(g_Point[i-1], g_Point[i]); } } //先排序，然后看有多少个不同的 qsort(g_PointOK,g_iPointOKCnt,sizeof(POINT),PointCmp); for (i = 1;i < g_iPointOKCnt;i++) { if (PointCmp(&g_PointOK[i-1],&g_PointOK[i]) != 0) { iPointCnt++; } } printf("%d\n",iPointCnt); } return 0;}
[解决办法]
[解决办法]