http://acm.hdu.edu.cn/showproblem.php?pid=1577判断三点共线公式为：(x2-x1)*(y3-y1)=(y2-y1)*(x3-x1)。刚开始我采用该公式判断，发现超时了，网上看了下发现了求公约数的方法，这种方法用到了相似三角形原理。
对于A、C两点它们之间如果存在整数点F与它们共线，则必有AB/BC=AE/EF，则AB与BC必有不为1的公约数，所以现在的问题由判断是否存在整数点共线变成横向距离和纵向距离是否互质了。这就很好判断了，以下是AC的代码。
1
#include <iostream>
2#include <algorithm>
3#include <string>
4#include <set>
5#include <cmath>
6#include <iomanip>
7using namespace std;
8
9int gcd(int a,int b)
10
{
11
int temp;
12 while(b)
13
{
14 temp=b;
15 b=a%b;
16 a=temp;
17
}
18 return a;
19
}
20
21int main()
22{
23 int l,x1,y1,x2,y2;
24 while(cin>>l,l)
25 {
26 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
27 if(abs(x2)>l || abs(y2)>l)
28 {
29 cout<<"Out Of Range\n";
30 continue;
31 }
32 if(gcd(abs(x1-x2),abs(y1-y2))==1)
33 cout<<"Yes\n";
34 else
35 cout<<"No\n";
36 }
37 return 0;
38}
posted on 2011-04-01 22:11
大大木马 阅读(355)
评论(0) 编辑 收藏 引用