Cod sursa(job #752779)

Utilizator SmarandaMaria Pandele Smaranda Data 29 mai 2012 15:31:54
Problema Rays Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#include <algorithm>
#include <math.h>
#define eps 1.e-14
#define pi 3.14

using namespace std;

struct Segment {
    double x,y1,y2;
};

struct Segment2 {
    double x,y;
};

Segment a[200001];
Segment2 s1[200001];
Segment2 s2[200001];

double unghi (double x , double y) {
    double tg,beta,sin,cos,d;
    tg=y/x;
    beta=tg;

    return beta;
}

bool cmp (Segment2 A , Segment2 B) {
    return (A.x-B.x<=-eps);
}

int main () {
    long n,i,c=0,u=0,o=0,num=0;
    double aux,st,dr;
	long f1,f2,f3;

    freopen ("rays.in","r",stdin);
    freopen ("rays.out","w",stdout);

    scanf("%ld",&n);
    for (i=1;i<=n;i++) {
        scanf("%ld%ld%ld",&f1,&f2,&f3);
		a[i].x=f1;
		a[i].y1=f2;
		a[i].y2=f3;
        if (a[i].y1-a[i].y2>eps) {
            aux=a[i].y1;
            a[i].y1=a[i].y2;
            a[i].y2=aux;
        }
        if (a[i].x>eps) {
            s1[++u].x=unghi(a[i].x,a[i].y1);
            s1[u].y=unghi(a[i].x,a[i].y2);
        }
        else {
            s2[++o].x=-unghi(a[i].x,a[i].y1);
            s2[o].y=-unghi(a[i].x,a[i].y2);
        }
    }
    sort (s1+1,s1+1+u,cmp);
    sort (s2+1,s2+1+o,cmp);
	st=s1[1].x;
	dr=s1[1].y;
    for (i=2;i<=u;i++) {
		if (s1[i].x-st>eps)
			st=s1[i].x;
		if (s1[i].y-dr<=-eps)
			dr=s1[i].y;
		if (st-dr>eps) {
			num++;
			st=s1[i].x;
			dr=s1[i].y;
			if (i==u)
				num--;
		}
	}
	num++;
	st=s2[1].x;
	dr=s2[1].y;
    for (i=2;i<=u;i++) {
		if (s2[i].x-st>eps)
			st=s2[i].x;
		if (s2[i].y-dr<=-eps)
			dr=s2[i].y;
		if (st-dr>eps) {
			num++;
			st=s2[i].x;
			dr=s2[i].y;
			if (i==u)
				num--;
		}
	}
	num++;
    printf("%ld\n",num);
    return 0;
}