格点判定 (Lattice Point or Not,UVa 11768) (未完成)

 1 #include <iostream>
 2 #include <string.h>
 3 #include <string>
 4 #include <fstream>
 5 #include <algorithm>
 6 #include <stdio.h>
 7 #include <vector>
 8 #include <queue>
 9 #include <set>
10 #include <cmath>
11 using namespace std;
12 const double eps = 1e-8;
13 const double pi=acos(-1.0);
14 const int INF=0x7fffffff;
15 unsigned long long uINF = ~0LL;
16 #define MAXN 1007
17 #define mod 1000000007
18 typedef long long LL;
19 LL gcd(LL a,LL b)
20 {
21     return b==0?a:gcd(b,a%b);
22 }
23 //ax+by=d;
24 void gcd(LL a,LL b,LL& d,LL& x,LL& y)
25 {
26     if(!b){d=a;x=1;y=0;}
27     else {gcd(b,a%b,d,y,x);y-=x*(a/b);}
28 }
29 LL a,b,c,d,x,y;
30 int main()
31 {
32     int T;
33     //freopen("0.in","r",stdin);
34     scanf("%d",&T);
35     while(T--)
36     {   //cout<<T<<' ';
37         int ans=0;
38         double x1,x2,y1,y2;
39         scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
40 
41         LL X1=x1>0?(x1+eps)*10:(x1-eps)*10;
42         LL X2=x2>0?(x2+eps)*10:(x2-eps)*10;
43         LL Y1=y1>0?(y1+eps)*10:(y1-eps)*10;
44         LL Y2=y2>0?(y2+eps)*10:(y2-eps)*10;
45         //cout<<X1<<' '<<X2<<' '<<Y1<<' '<<Y2<<endl;
46         a=(Y1-Y2);
47         b=(X2-X1);
48         c=(X1*(Y1-Y2)-Y1*(X1-X2));
49         //d=gcd(a,b);
50         if(X1>X2)swap(X1,X2);
51         if(Y1>Y2)swap(Y1,Y2);
52         if(a==0&&Y1%10==0){ans+=(X2-X1)/10;if(X1%10==0||X2%10==0)ans++;
53                 cout<<ans<<endl;continue;}
54         else if(a==0){cout<<0<<endl;continue;}
55         if(b==0&&X1%10==0){ans+=(Y2-Y1)/10;if(Y1%10==0||Y2%10==0)ans++;
56                 cout<<ans<<endl;continue;}
57         else if(b==0){cout<<0<<endl;continue;}
58         //cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<x<<' '<<y<<endl;
59         gcd(a,b,d,x,y);
60         //cout<<c<<' '<<d<<endl;
61         if(c%(d*10)==0)
62         {
63 
64         x=x*(c/d);y=y*(c/d);
65         LL k1,k2;
66         k1=(X1-x)/(b/d*10);k2=(X2-x)/(b/d*10);
67         if(k1>k2)swap(k1,k2);
68         //cout<<k1<<' '<<k2<<endl;
69         x/=10;
70         //cout<<x<<' '<<(b/d)<<endl;
71         for(LL i=k1;i<=k2;i++)
72         {
73             LL temp=10*(x+i*(b/d));
74             if(min(X1,X2)<=temp&&temp<=max(X1,X2))ans++;
75         }
76         /*for(LL i=X1;i<=X2;i+=10)
77         {
78             if(i%10!=0)i+=(10-i%10);
79             LL temp=(i-x)/(b/d);
80             LL Y=y-(a/d)*temp;
81             if(Y%10==0)ans++;
82             //LL X=x+(b/d)*i;
83             //LL Y=y-(a/d)*i;
84             //if(X1<=X&&X<=X2&&Y1<=Y&&Y<=Y2&&X%10==0&&Y%10==0)
85             //{ans++;cout<<X<<' '<<Y<<endl;}
86         }*/
87         cout<<ans<<endl;
88         }
89         else cout<<0<<endl;
90     }
91 
92     return 0;
93 }
改了好久还是WA 先放一放有时间再来搞~~