[CodeForces-1036E] Covered Points 暴力 GCD 求交点

　　题意：

　　　　在二维平面上给出n条不共线的线段，问这些线段总共覆盖到了多少个整数点

　　

　　解法：

　　　　　　用GCD可求得一条线段覆盖了多少整数点，然后暴力枚举线段，求交点，对于相应的

　　　　整数交点，结果-1即可

　　

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<cmath>

 #include<vector>

 #include<queue>

 #include<set>

 #include<map>

 using namespace std;

 #define eps 1e-6

 #define For(i,a,b) for(int i=a;i<=b;i++)

 #define Fore(i,a,b) for(int i=a;i>=b;i--)

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define mkp make_pair

 #define pb push_back

 #define sz size()

 #define met(a,b) memset(a,b,sizeof(a))

 #define iossy ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

 #define fr freopen

 #define pi acos(-1.0)

 #define Vector Point

 typedef pair<int,int> pii;

 const long long linf=1LL<<;

 const int iinf=<<;

 const double dinf=1e17;

 const int Mod=1e9+;

 typedef long long ll;

 typedef long double ld;

 const int maxn=;

 int n;

 struct Point{

     ll x,y;

     int id;

     Point(ll x=,ll y=):x(x),y(y) {}

     Point operator - (const Point &a)const { return Point(x-a.x,y-a.y);}

     bool operator == (const Point &a)const { return x==a.x && y==a.y; }

 };

 ll Cross(Vector a,Vector b){

     return a.x*b.y-a.y*b.x;

 }

 ll Dot(Vector a,Vector b) {

     return a.x*b.x+a.y*b.y;

 }

 bool onsg(Point p,Point a1,Point a2){

     return Cross(a1-p,a2-p)== && Dot(a1-p,a2-p)<;

 }

 void ck(ll &c){

     if(c>) c=;

     else if(c<) c=-;

 }

 int Ins(Point a1,Point a2,Point b1,Point b2){

     if(a1==b1 || a1==b2 || a2==b1 || a2==b2) return ;

     if(onsg(a1,b1,b2) || onsg(a2,b1,b2) || onsg(b1,a1,a2) || onsg(b2,a1,a2)) return ;

     ll c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1);

     ll c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);

     ck(c1);ck(c2);ck(c3);ck(c4);

     return c1*c2< && c3*c4<;

 }

 set<pair<ll,ll> >c;

 void chk(Point p,Vector v,Point q,Vector w){

     Vector u=p-q;

     ll v1=Cross(w,u),v2=Cross(v,w);

     if(abs(v1*v.x)%v2!= || abs(v1*v.y)%v2!=) return ;

     ll xx,yy;

     xx=p.x+v.x*v1/v2;yy=p.y+v.y*v1/v2;

     c.insert(mkp(xx,yy));

 }

 struct segm{

     Point p1,p2;

 };

 segm ss[maxn];

 Point p1,p2;

 void solve(){

     iossy;

     cin>>n;

     int ans=;

     For(i,,n){

         cin>>p1.x>>p1.y>>p2.x>>p2.y;

         ss[i].p1=p1;ss[i].p2=p2;

         ans+=__gcd(abs(ss[i].p2.x-ss[i].p1.x),abs(ss[i].p2.y-ss[i].p1.y))+;

     }

     For(i,,n){

         c.clear();

         For(j,i+,n){

             int ct=Ins(ss[i].p1,ss[i].p2,ss[j].p1,ss[j].p2);

             if(ct) chk(ss[i].p1,ss[i].p2-ss[i].p1,ss[j].p1,ss[j].p2-ss[j].p1);

         }

         ans-=c.sz;

     }

     //cout<<ans-c.sz<<endl;

     cout<<ans<<endl;

 }

 int main(){

     int t=;

    // For(i,1,t) printf("Case #%d: ",i);

     solve();

     return ;

 }

[CodeForces-1036E] Covered Points 暴力 GCD 求交点的相关教程结束。