Cod sursa(job #369964)

Utilizator victor.ionescuIonescu Victor Cristian victor.ionescu Data 29 noiembrie 2009 21:41:17
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi("rays.in");
ofstream fo("rays.out");
int N,lst=0,ldr=0;
struct segment{
	int x,y1,y2;
} vst[200010],vdr[200010];

inline int min(int a,int b){ return a<b?a:b; }
inline int max(int a,int b){ return a>b?a:b; }

inline bool cmp(const segment &A, const segment &B){
	if (((long long)A.y1*B.x)!=((long long)A.x*B.y1)) return ((long long)A.y1*B.x)<((long long)A.x*B.y1); else 
		return ((long long)A.y2*B.x)>((long long)A.x*B.y2);
}


int main(){
	fi>>N;
	int x,y,z;
	for (int i=1;i<=N;++i){
		fi>>x>>y>>z;
		if (x<0){
			++lst;
			vst[lst].x=x;
			vst[lst].y1=max(y,z);
			vst[lst].y2=min(y,z);
		} else {
			++ldr;
			vdr[ldr].x=x;
			vdr[ldr].y1=min(y,z);
			vdr[ldr].y2=max(y,z);
		}
	}
	int rez=0,xst,yst,xdr,ydr;
	if (lst){
		sort(vst+1,vst+lst+1,cmp);
		++rez;
		xst=xdr=vst[1].x;
		yst=vst[1].y1;
		ydr=vst[1].y2;
		for (int i=2;i<=lst;++i){
			if (((long long)vst[i].y1*xst)>((long long)vst[i].x*yst)) { xst=vst[i].x; yst=vst[i].y1; }
			if (((long long)vst[i].y2*xdr)<((long long)vst[i].x*ydr)) { xdr=vst[i].x; ydr=vst[i].y2; }
			if (((long long)yst*xdr)>((long long)xst*ydr)){ ++rez; xst=xdr=vst[i].x; yst=vst[i].y1;ydr=vst[i].y2; }
		}
	}
	if (ldr){
		sort(vdr+1,vdr+ldr+1,cmp);
		++rez;
		xst=xdr=vdr[1].x;
		yst=vdr[1].y1;
		ydr=vdr[1].y2;
		for (int i=2;i<=ldr;++i){
			if (((long long)vdr[i].y1*xst)>((long long)yst*vdr[i].x)) { xst=vdr[i].x; yst=vdr[i].y1; }
			if (((long long)vdr[i].y2*xdr)<((long long)ydr*vdr[i].x)) { xdr=vdr[i].x; ydr=vdr[i].y2; }
			if (((long long)yst*xdr)>((long long)ydr*xst)){ ++rez; xst=xdr=vdr[i].x; yst=vdr[i].y1; ydr=vdr[i].y2; }
		}
	}
	fo<<rez<<"\n";
	fo.close();
	return 0;
}