题意：
在二维平面上给出n条不共线的线段，问这些线段总共覆盖到了多少个整数点
解法：
用GCD可求得一条线段覆盖了多少整数点，然后暴力枚举线段，求交点，对于相应的
整数交点，结果-1即可
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #include<cmath> 6 #include<vector> 7 #include<queue> 8 #include<set> 9 #include<map> 10 using namespace std; 11 #define eps 1e-6 12 #define For(i,a,b) for(int i=a;i<=b;i++) 13 #define Fore(i,a,b) for(int i=a;i>=b;i--) 14 #define lson l,mid,rt<<1 15 #define rson mid+1,r,rt<<1|1 16 #define mkp make_pair 17 #define pb push_back 18 #define sz size() 19 #define met(a,b) memset(a,b,sizeof(a)) 20 #define iossy ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) 21 #define fr freopen 22 #define pi acos(-1.0) 23 #define Vector Point 24 typedef pair<int,int> pii; 25 const long long linf=1LL<<62; 26 const int iinf=1<<30; 27 const double dinf=1e17; 28 const int Mod=1e9+9; 29 typedef long long ll; 30 typedef long double ld; 31 const int maxn=1000005; 32 int n; 33 struct Point{ 34 ll x,y; 35 int id; 36 Point(ll x=0,ll y=0):x(x),y(y) {} 37 Point operator - (const Point &a)const { return Point(x-a.x,y-a.y);} 38 bool operator == (const Point &a)const { return x==a.x && y==a.y; } 39 }; 40 ll Cross(Vector a,Vector b){ 41 return a.x*b.y-a.y*b.x; 42 } 43 ll Dot(Vector a,Vector b) { 44 return a.x*b.x+a.y*b.y; 45 } 46 bool onsg(Point p,Point a1,Point a2){ 47 return Cross(a1-p,a2-p)==0 && Dot(a1-p,a2-p)<0; 48 } 49 void ck(ll &c){ 50 if(c>0) c=1; 51 else if(c<0) c=-1; 52 } 53 int Ins(Point a1,Point a2,Point b1,Point b2){ 54 if(a1==b1 || a1==b2 || a2==b1 || a2==b2) return 1; 55 if(onsg(a1,b1,b2) || onsg(a2,b1,b2) || onsg(b1,a1,a2) || onsg(b2,a1,a2)) return 1; 56 ll c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1); 57 ll c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1); 58 ck(c1);ck(c2);ck(c3);ck(c4); 59 return c1*c2<0 && c3*c4<0; 60 } 61 set<pair<ll,ll> >c; 62 void chk(Point p,Vector v,Point q,Vector w){ 63 Vector u=p-q; 64 ll v1=Cross(w,u),v2=Cross(v,w); 65 if(abs(v1*v.x)%v2!=0 || abs(v1*v.y)%v2!=0) return ; 66 ll xx,yy; 67 xx=p.x+v.x*v1/v2;yy=p.y+v.y*v1/v2; 68 c.insert(mkp(xx,yy)); 69 } 70 struct segm{ 71 Point p1,p2; 72 }; 73 segm ss[maxn]; 74 Point p1,p2; 75 void solve(){ 76 iossy; 77 cin>>n; 78 int ans=0; 79 For(i,1,n){ 80 cin>>p1.x>>p1.y>>p2.x>>p2.y; 81 ss[i].p1=p1;ss[i].p2=p2; 82 ans+=__gcd(abs(ss[i].p2.x-ss[i].p1.x),abs(ss[i].p2.y-ss[i].p1.y))+1; 83 } 84 For(i,1,n){ 85 c.clear(); 86 For(j,i+1,n){ 87 int ct=Ins(ss[i].p1,ss[i].p2,ss[j].p1,ss[j].p2); 88 if(ct) chk(ss[i].p1,ss[i].p2-ss[i].p1,ss[j].p1,ss[j].p2-ss[j].p1); 89 } 90 ans-=c.sz; 91 } 92 //cout<<ans-c.sz<<endl; 93 cout<<ans<<endl; 94 } 95 int main(){ 96 int t=1; 97 // For(i,1,t) printf("Case #%d: ",i); 98 solve(); 99 return 0; 100 }