shipu

UVA 866 - Intersecting Line Segments

Shipu Ahamed's photo
Shipu Ahamed
·

3 min read

Problem PDF

Solution:

/******************************************************************
***   Problem       :                                           ***
***   Author        : Shipu Ahamed (Psycho Timekiller)          ***
***   E-mail        : shipuahamed01@gmail.com                   ***
***   University    : BUBT,Dept. of CSE                         ***
***   Team          : BUBT_Psycho                               ***
***   My Blog       : http://shipuahamed.blogspot.com           ***
***   Facebook      : http://www.facebook.com/DeesheharaShipu   ***
******************************************************************/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define pi 2*acos(0.0)
#define all(v) v.begin(),v.end()

//input
#define si(t) scanf("%d",&t)
#define sl(t) scanf("%lld",&t)
#define sf(t) scanf("%f",&t)
#define sd(t) scanf("%lf",&t)
#define sc(c) scanf("%c",&c)
#define sii(a,b) scanf("%d%d",&a,&b)
#define sll(a,b) scanf("%lld%lld",&a,&b)

//Output
#define P(a) printf("%d\n",a)
#define PL(a) printf("%lld\n",a)
#define PF(a) printf("%f\n",a)
#define PD(a) printf("%lf\n",a)
#define PS(a) printf("%s\n",a)
#define PSN(a) printf("%s ",a)
#define PN(a) printf("%d ",a)
#define PLN(a) printf("%lld ",a)
#define PFN(a) printf("%f ",a)
#define PDN(a) printf("%lf ",a)
#define PP(a,b) printf("%d %d\n",a,b)
#define PPN(a,b) printf("%d %d ",a,b)
#define PPL(a,b) printf("%lld %lld\n",a,b)
#define PPLN(a,b) printf("%lld %lld ",a,b)

#define CP(a) cout< vi;
typedef  vector vll;
typedef  vector vs;
typedef  set si;
typedef  set ss;
typedef  map mii;
typedef  map mll;
typedef  map msi;
typedef  map mci;

template string toString( T Number ){stringstream st;st << Number;return st.str();}
template  T SOD(T n) {__typeof(n) sum=0;for(__typeof(n) i=1;i*i<=n;i++)sum+=(n%i)?0:((i*i==n)?i:i+n/i);return sum;}

//For Define
#define forab(i,a,b) for(__typeof(b) i=(a);i<=(b);i++)
#define for0(i,n) forab(i,0,(n)-1)
#define for1(i,n) forab(i,1,n)
#define rforab(i,b,a) for(__typeof(b) i=(b);i>=(a);i--)
#define rfor0(i,n) rforba(i,(n)-1,0)
#define rfor1(i,n) rforba(i,n,1)
#define forstl(i,s) for(__typeof((s).end()) i=(s).begin(); i != (s).end(); i++)

//Debug
#define dbg(x) cout << #x << " -> " << (x) << endl;
#define dbgsarr(i,a) cout<<#a<<"["< "< "< "<>p ; return p;}

ll pow(ll a,ll b, ll m) { ll res = 1; while(b) { if(b & 1) { res = ( (res % m) * (a % m) ) %m ; } a= ((a%m) * (a%m)) %m; b >>= 1; } return res; }
ll modInverse(ll a, ll m){return pow(a,m-2,m);}

////============ CONSTANT ===============////
#define mx7   10000007
#define mx6   1000006
#define mx5   100005
#define inf   1<<30                                           //infinity value
#define eps   1e-9
#define mx    (100010)
#define mod   1000000007
////=====================================////

int tarea(int x1, int y1, int x2, int y2, int x3, int y3){ //i don't use struct bcz it's tough for me.
    return x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-y3*x1;
}

bool online(int x1,int y1,int x2,int y2,int x3,int y3)
{
    int  minx,miny,maxx,maxy;
    minx=min(x1,x2);miny=min(y1,y2);
    maxx=max(x1,x2);maxy=max(y1,y2);

    if(minx<=x3 && maxx>=x3 && miny<=y3 && maxy>=y3 )
        return true;
    else
    return false;
}

bool intersection(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4)
{
    int a1=tarea(x3,y3,x4,y4,x1,y1);
    int a2=tarea(x3,y3,x4,y4,x2,y2);
    int a3=tarea(x1,y1,x2,y2,x3,y3);
    int a4=tarea(x1,y1,x2,y2,x4,y4);

//    PP(a1,a2),PP(a3,a4);
//    P(online(x3,y3,x4,y4,x1,y1));
//    nl;
    if(a1*a2<0 && a3*a4<0) return true;
    else if(a1==0 && online(x3,y3,x4,y4,x1,y1)) return true;
    else if(a2==0 && online(x3,y3,x4,y4,x2,y2)) return true;
    else if(a3==0 && online(x1,y1,x2,y2,x3,y3)) return true;
    else if(a4==0 && online(x1,y1,x2,y2,x4,y4)) return true;
    else
        return false;
}

struct line
{
    int x1,y1,x2,y2;
};

int main()
{
    int t;
    si(t);
    while(t--)
    {
        vectorv;
        line p;

        int n;
        si(n);
        while(n--)
        {
            sii(p.x1,p.y1),sii(p.x2,p.y2);
            v.pb(p);
        }

        n=sz(v);

        int res=0;
        for0(i,n)
        {
//            PP(v[i].x1,v[i].y1),PP(v[i].x2,v[i].y2);
            int cnt=0;
            for0(j,n)
            {
                if(i==j) continue;

                if(intersection(v[i].x1,v[i].y1,v[i].x2,v[i].y2,v[j].x1,v[j].y1,v[j].x2,v[j].y2 ))
                    cnt++;
            }
            res += cnt+1;
        }

        P(res);
        if(t)
            nl;

    }

    return 0;
}

https://github.com/Shipu/OnlineJudgeProblemSolutionWithCPlusPlus/tree/master/uva/866/866.cpp

Competitive programming