Cod sursa(job #1236715)

Utilizator armandpredaPreda Armand armandpreda Data 2 octombrie 2014 15:35:04
Problema Next Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define eps 1.e-14
#define INF 1.e9

using namespace std;

class POINT
{
    private: int x,y;
    public:
    POINT(){x=0,y=0;}
    int getx(){return x;}
    int gety(){return y;}
    void set(int x0,int y0)
    {
        x=x0;y=y0;
    }
    int ccw(const POINT & P2,const POINT & P3)
    {
        long long cp;
        cp=1ll*(P2.x-x)*(P3.y-P2.y)-(P2.y-y)*(P3.x-P2.x);
        if(cp)
            if(cp>0)
                return 1;
            else
                return -1;
        else
            return 0;
    }
    bool in_box(const POINT & P1,const POINT & P2)
    {
        POINT D1,D2;
        D1.x=min(P1.x,P2.x);
        D1.y=min(P1.y,P2.y);
        D2.x=max(P1.x,P2.x);
        D2.y=max(P1.y,P2.y);
        return x>=D1.x and y>=D1.y and x<=D2.x and y<=D2.y;
    }
    friend bool intersectia(POINT & P1,POINT & P2,POINT & P3,POINT & P4)
    {
        return P3.ccw(P1,P2)*P4.ccw(P1,P2)<0 and P1.ccw(P3,P4)*P2.ccw(P3,P4)<0;
        if(P3.ccw(P1,P2)*P4.ccw(P1,P2)==0 or P1.ccw(P3,P4)*P2.ccw(P3,P4)==0)
            return P1.in_box(P3,P4) or P2.in_box(P3,P4) or P3.in_box(P1,P2) or P4.in_box(P1,P2);
    }
};
vector <POINT> v;
int main()
{
    int n,i,j,x,y,nr,s=0;
    POINT temp;
    scanf("%d",&n);
    for(i=1;i<=n*2;++i)
    {
        scanf("%d%d",&x,&y);
        temp.set(x,y);
        v.push_back(temp);
    }
    for(i=0;i<n*2;i+=2)
    {
        nr=1;
        for(j=0;j<n*2;j+=2)
            if(i!=j and intersectia(v[i],v[i+1],v[j],v[j+1]))
                nr++;
        s+=nr;
    }
    printf("%d",s);
    return 0;
}