Cod sursa(job #752793)

Utilizator SmarandaMaria Pandele Smaranda Data 29 mai 2012 16:24:15
Problema Rays Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
#include <algorithm>
#include <math.h>
using namespace std;
struct Segment2 {
    double x,y;
};


Segment2 s1[200005];
Segment2 s2[200005];

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

int main () {
    long n,i,c=0,u=0,o=0,num=0,x,y1,y2;
    double aux,st,dr,rays;
	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",&x,&y1,&y2);
        if (y1>y2) {
            aux=y1;
            y1=y2;
            y2=aux;
        }
        if (x>0) {
            s1[++u].x=(double)y1/x;
            s1[u].y=(double)y2/x;
        }
        else {
            s2[++o].x=-(double)y1/x;
            s2[o].y=-(double)y2/x;
        }
    }
    sort (s1+1,s1+1+u,cmp);
    sort (s2+1,s2+1+o,cmp);
	rays=s1[1].y;
	num=0;
	s1[u+1].x=2000000000;
	for (i=2;i<=u+1;i++)
		if (rays<s1[i].x) {
			num++;
			rays=s1[i].y;
		}
		else
			if (s1[i].y<rays)
				rays=s1[i].y;
	rays=s2[1].y;
	s2[o+1].x=2000000000;
	for (i=2;i<=o+1;i++) {
		if (rays<s2[i].x) {
			num++;
			rays=s2[i].y;
		}
		else
			if (s2[i].y<rays)
				rays=s2[i].y;
	}
    printf("%ld\n",num);
    return 0;
}