Cod sursa(job #2323946)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 20 ianuarie 2019 02:50:26
Problema Rays Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 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
 
*/

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

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

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) == 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);
    
//    for(auto it : seg){
//        out<<it.a.x<<" "<<it.a.y<<"   "<<it.b.x<<" "<<it.b.y<<'\n';
//    }
//
//    out<<cmp(MakePoint(-2, 3), MakePoint(-2, 7));
    
    point last = seg[0].b;
    int sol = 1;
    for(int i = 0; i < seg.size(); ++ i){
        if(cmp(last, seg[i].a)){
            ++ sol;
            last = seg[i].b;
        }
    }
    out<<sol;
    
    return 0;
}