Cod sursa(job #120214)

Utilizator andrei.12Andrei Parvu andrei.12 Data 4 ianuarie 2008 17:07:12
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 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, pi = 3.14159265;
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 ind, citire v[]){
	int st = 1, nr = 0;
	double end, tg, ug;
	
	for (int i = 1; i <= ind; i ++){
		x = ab(v[i].x);
		
		yy1 = ab(v[i].yy1);
		tg = (double)x / yy1;
		ug = atan(tg), ug = 180*ug/pi;
		//fprintf(stderr, "cat e unghiu %lf\n", ug);
		if (v[i].yy1 > 0)
			q[++nr].st = 180 - ug;
		else
			q[++nr].st = ug;
		//fprintf(stderr, "%lf -> %lf \n", atan(tg)*180/pi, q[nr].st);
		
		yy2 = ab(v[i].yy2);
		tg = (double)x / yy2;
		ug = atan(tg), ug = 180*ug/pi;
		if (v[i].yy2 > 0)
			q[nr].end = 180 - ug;
		else
			q[nr].end = ug;
	}
	
	sort(q+1, q+nr+1, cmp);
	
	//for (int i = 1; i <= nr; i ++)
		//fprintf(stderr, "%lf %lf\n", q[i].st, q[i].end);
	end = q[1].end;
	for (int i = 2; i <= nr; i ++){
		if (q[i].st > end)
			st ++;
		end = max(end, q[i].end);
	}
	
	//fprintf(stderr, "%d\n", st);
	sol += st;
	//fprintf(stderr, "\n");
}
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 (yy1 > yy2){
			int aux = yy1;
			yy1 = yy2, yy2 = aux;
		}
		
		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;
}