Pagini recente » Cod sursa (job #2565351) | Cod sursa (job #153319) | Cod sursa (job #904517) | Cod sursa (job #1794284) | Cod sursa (job #1767388)
#include <cstdio>
#include <algorithm>
#define NMax 200000
#define mp make_pair
#define DIM 10000
using namespace std;
char buff[DIM];
int poz;
struct seg { int x,y1,y2; };
seg st[NMax+1], dr[NMax+1];
int nr,nl,ans;
void Read(int& numar)
{
char sgn='+';
numar = 0;
while(buff[poz]<'0'||buff[poz]>'9')
{
sgn = buff[poz];
if(++poz==DIM) fread(buff,1,DIM,stdin),poz=0;
}
while(buff[poz]>='0'&&buff[poz]<='9')
{
numar = numar*10 + buff[poz] - '0';
if(++poz==DIM) fread(buff,1,DIM,stdin),poz=0;
}
if(sgn=='-') numar=-numar;
}
bool cmp1(const seg A, const seg B )
{
if( 1LL*A.y1*B.x==1LL*A.x*B.y1 ) return 1LL*A.y2*B.x<1LL*A.x*B.y2;
return 1LL*A.y1*B.x<1LL*A.x*B.y1;
}
bool cmp2(const seg A, const seg B )
{
if( 1LL*A.x*B.y1==1LL*A.y1*B.x ) return 1LL*A.x*B.y2==1LL*A.y2*B.x;
return 1LL*A.x*B.y1<1LL*A.y1*B.x;
}
void swap(int& a, int& b)
{
int aux = a;
a = b;
b = aux;
}
void Solve_dr()
{
int i,j,f,lx,ly,rx,ry;
if(nr==0) return;
f = 1;
sort(dr+1,dr+nr+1,cmp1);
lx = dr[1].x; ly = dr[1].y1;
rx = dr[1].x; ry = dr[1].y2;
for(i = 2; i <= nr; ++i)
{
if( 1LL*ly*dr[i].x < 1LL*lx*dr[i].y1 ) { lx = dr[i].x; ly = dr[i].y1; }
if( 1LL*ry*dr[i].x > 1LL*rx*dr[i].y2 ) { rx = dr[i].x; ry = dr[i].y2; }
if( 1LL*ly*rx > 1LL*lx*ry )
{
lx = dr[i].x; ly = dr[i].y1;
rx = dr[i].x; ry = dr[i].y2;
++f;
}
}
ans = ans + f;
}
void Solve_st()
{
int i,j,f,lx,ly,rx,ry;
if(nl==0) return;
f = 1;
sort(st+1,st+nl+1,cmp2);
lx = st[1].x; ly = st[1].y1;
rx = st[1].x; ry = st[1].y2;
for(i = 2; i <= nl; ++i)
{
if( 1LL*lx*st[i].y1 < 1LL*ly*st[i].x ) { lx = st[i].x; ly = st[i].y1; }
if( 1LL*rx*st[i].y2 > 1LL*ry*st[i].x ) { rx = st[i].x; ry = st[i].y2; }
if( 1LL*ly*rx < 1LL*lx*ry )
{
lx = st[i].x; ly = st[i].y1;
rx = st[i].x; ry = st[i].y2;
++f;
}
}
ans = ans + f;
}
int main(){
freopen("rays.in","r",stdin);
freopen("rays.out","w",stdout);
int i,N,x,y1,y2;
scanf("%d",&N);
for(nr = nl = 0, i = 1; i <= N; ++i)
{
Read(x);
Read(y1);
Read(y2);
if( y1 > y2 ) swap(y1,y2);
if(x>0) { dr[++nr].x = x; dr[nr].y1 = y1; dr[nr].y2 = y2; }
else { st[++nl].x = x; st[nl].y1 = y1; st[nl].y2 = y2; }
}
Solve_dr();
Solve_st();
printf("%d\n", ans);
return 0;
}