Cod sursa(job #935295)

Utilizator addy01adrian dumitrache addy01 Data 2 aprilie 2013 18:42:04
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define infinit 1<<30
using namespace std;
struct point
{
    int x,y1,y2;
}v[200010];

struct chestie
{
    float x, y;
} p1[200010], p2[200010];

float panta1(point p1,point p2)
{
    if(p1.x==p2.x)
        return infinit;
    return (p2.y1-p1.y1)*1.0/(p2.x-p1.x);
}

float panta2(point p1,point p2)
{
    if(p1.x==p2.x)
        return infinit;
    return (p2.y2-p1.y2)*1.0/(p2.x-p1.x);
}

inline bool comp (const chestie &A, const chestie &B)
{
    return A.x < B.x;
}

int main()
{
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);
    int i,n,k1=0,k2=0, Ans = 2, aux;
    float last;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d%d",&v[i].x,&v[i].y1,&v[i].y2);
        if(v[i].y1>v[i].y2)
        {
            aux=v[i].y1;
            v[i].y1=v[i].y2;
            v[i].y2=aux;
        }
    }
  for(i=1;i<=n;i++)
    if(v[i].x < 0)
        {
            ++ k1;
            p1[k1].x=-(float)v[i].y1*1.0/v[i].x;
            p1[k1].y=-(float)v[i].y2*1.0/v[i].x;
        }
        else
        {
            ++ k2;
            p2[k2].x=(float)v[i].y1*1.0/v[i].x;
            p2[k2].y=(float)v[i].y2*1.0/v[i].x;
        }

    sort (p1 + 1, p1 + k1 + 1, comp);
    sort (p2 + 1, p2 + k2 + 1, comp);

    last = p1[1].y;
    for (i = 2; i <= k1; i ++)
        if (p1[i].x > last || p1[i].y < last){
            if (p1[i].x > last)
                Ans ++;

            last = p1[i].y;
        }

    last = p2[1].y;
    for (i = 2; i <= k2; i ++)
        if (p2[i].x > last || p2[i].y < last){
            if (p2[i].x > last)
                Ans ++;

            last = p2[i].y;
        }

    cout << Ans;

    return 0;
}