Cod sursa(job #2323949)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 20 ianuarie 2019 03:06:00
Problema Rays Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream in ("rays.in");
ofstream out("rays.out");

int n;

struct point{
    int x, y;
};

point MakePoint(int x, int y){
    point aux;
    aux.x = x;
    aux.y = y;
    return aux;
}

struct segment{
    point a, b;
};

segment MakeSegment(point a, point b){
    segment aux;
    aux.a = a;
    aux.b = b;
    return aux;
}

vector<segment> seg;

int GetCadran(point a){
    if(a.x > 0){
        if(a.y > 0)
            return 1;
        return 4;
    }
    if(a.y > 0)
        return 2;
    return 3;
}

point origin = MakePoint(0, 0);

/*
 
 x1 y1 1
 x2 y2 1
 x3 y3 1
 x1 y1 1
 x2 y2 1
 
 x1y2 + x2y3 + x3y1 - x3y2 - x1y3 - x2y1
 
*/

long long det(point a, point b)
{
    long long res = 1LL * a.x * b.y;
    res = res - 1LL * a.y * b.x;
    return res;
}

long long dist(point a){
    long long res = 1LL * a.x * a.x;
    res = res + 1LL * a.y * a.y;
    return res;
}

bool cmp(point a, point b){
    int cadranA = GetCadran(a);
    int cadranB = GetCadran(b);
    
    if(cadranA == cadranB){
        long long determinant = det(a, b);
        if(determinant == 0){
            return dist(a) < dist(b);
        }
        return determinant > 0;
    }
    
    return cadranA < cadranB;
}

bool equal(point a, point b){
    int cadranA = GetCadran(a);
    int cadranB = GetCadran(b);
    
    if(cadranA == cadranB){
        return det(a, b) == (long long) 0;
    }
    
    return 0;
}

bool sortCmp(segment a, segment b){
    if(equal(a.b, b.b))
        return cmp(a.a, b.a);
    return cmp(a.b, b.b);
        
}

int main(int argc, const char * argv[]) {
    in>>n;
    for(int i = 1; i <= n; ++ i){
        int x, Y1, Y2;
        in>>x>>Y1>>Y2;
        seg.push_back(MakeSegment(MakePoint(x, Y1), MakePoint(x, Y2)));
        if(cmp(seg.back().b, seg.back().a))
            swap(seg.back().a, seg.back().b);
    }
    
    sort(seg.begin(), seg.end(), sortCmp);

    
    point last = seg[0].b;
    int sol = 1;
    for(int i = 1; i < seg.size(); ++ i){
        if(cmp(last, seg[i].a) || equal(last, seg[i].a)){
            ++ sol;
            last = seg[i].b;
        }
    }
    out<<sol;
    
    return 0;
}