Cod sursa(job #1745448)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 21 august 2016 21:45:09
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <bits/stdc++.h>
#define nmax 200001
using namespace std;
ifstream fin("rays.in");
ofstream fout("rays.out");
struct ev
{
    int x,y1,y2;
    double t;
};
ev st[nmax],dr[nmax];
int n,lgs,lgd,i,x,y,y2,glont,f;
queue<ev>e;
double t;
int qx(ev a, ev b)
{
    return a.t>b.t;
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>x>>y>>y2;
        if(y>y2)swap(y,y2);
        if(x<0)
            st[++lgs]={x,y,y2,(double)y2/x};
        else
            dr[++lgd]={x,y,y2,(double)y2/x};
    }
    sort(st+1,st+lgs+1,qx);
    if(lgs)
    {
        glont++;
        x=st[1].x;
        y=st[1].y2;
        for(i=2;i<=lgs;i++)
            if((double)y/x>(double)st[i].y1/st[i].x)glont++,x=st[i].x,y=st[i].y2;
    }
    sort(dr+1,dr+lgd+1,qx);
    reverse(dr+1,dr+lgd+1);
    if(lgd)
    {
        glont++;
        x=dr[1].x;
        y=dr[1].y2;
        for(i=2;i<=lgd;i++)
            if((double)y/x<(double)dr[i].y1/dr[i].x)glont++,x=dr[i].x,y=dr[i].y2;
    }
    fout<<glont<<"\n";
    return 0;
}