Cod sursa(job #120182)

Utilizator andrei.12Andrei Parvu andrei.12 Data 4 ianuarie 2008 14:53:08
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define lg 200005

using namespace std;

int n, i, x, yy1, yy2, nr, st, ind1, ind2, sol;
double tg, end;
struct citire{
	int x, yy1, yy2;
};
citire v1[lg], v2[lg];
struct interval{
	double st, end;
};
interval q[lg];
inline int ab(int a){
	if (a < 0)
		return (-a);
	return a;
}
int cmp(interval a, interval b){
	if (a.st != b.st)
		return (a.st < b.st);
	return (a.end < b.end);
}
void rezolv(int ind1, citire v1[]){
	int st = 0, nr = 0;
	double end, tg;
	
	for (int i = 1; i <= ind1; i ++){
		x = ab(v1[i].x);
		
		yy1 = ab(v1[i].yy1);
		tg = (double)x / yy1;
		q[++nr].st = atan(tg);
		
		yy2 = ab(v1[i].yy2);
		tg = (double)x / yy2;
		q[nr].end = atan(tg);
	}
	
	sort(q+1, q+nr+1, cmp);
	
	end = q[1].end;
	for (int i = 2; i <= nr; i ++){
		if (q[2].st > end)
			st ++;
		end = q[2].end;
	}
	
	//printf("%d\n", st);
	sol += st;
}
int main()
{
	freopen("rays.in", "rt", stdin);
	freopen("rays.out", "wt", stdout);
	
	scanf("%d", &n);
	
	for (i = 1; i <= n; i ++){
		scanf("%d%d%d", &x, &yy1, &yy2);
		
		if (x < 0){
			v1[++ind1].x = x;
			v1[ind1].yy1 = yy1;
			v1[ind1].yy2 = yy2;
		}
		else{
			v2[++ind2].x = x;
			v2[ind2].yy1 = yy1;
			v2[ind2].yy2 = yy2;
		}
	}

	rezolv(ind1, v1);
	rezolv(ind2, v2);
	
	printf("%d\n", sol);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}