Cod sursa(job #951046)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 18 mai 2013 23:58:54
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
const char iname[] = "rays.in";
const char oname[] = "rays.out";
ifstream fin(iname);
ofstream fout(oname);
int N, i, j, a, b, c, ANS, st, dr;
pair <int,int> P;
struct segment{int xAB, yA, yB; segment(){}; segment(int X, int Y, int Z){xAB = X; yA = Y; yB = Z;}; }D;
vector <segment> Xst, Xdr;
struct cmp{
    bool operator ()(const segment &A, const segment &B) const
    {
        if (1LL*(A.yB - P.y) * (B.xAB - P.x) < 1LL*(A.xAB - P.x) * (B.yB - P.y)) return 1;
        return 0;
    }
};
inline void Solve(vector <segment> v){
    sort (v.begin(), v.end(), cmp());
    if (v.size() != 0){
        ++ANS; st = v[0].xAB; dr = v[0].yB;
        for (i = 1; i < v.size(); ++i){
            if (1LL* st * v[i].yA > 1LL* dr * v[i].xAB)
            {
                ++ANS;
                st = v[i].xAB; dr = v[i].yB;
            }
        }
    }
}
int main(){
    fin >> N; P.x = P.y = 0;
    while (N--){
        fin >> D.xAB >> D.yA >> D.yB;
        if (D.yA > D.yB) swap(D.yA, D.yB);
        if (D.xAB < 0){
            D.xAB = -D.xAB;
            Xst.push_back(D);
        }
        else
            Xdr.push_back(D);
    }
    Solve(Xst); Solve(Xdr);
    fout << ANS << '\n';
    return 0;
}