Pagini recente » Cod sursa (job #252838) | Cod sursa (job #3287026) | Cod sursa (job #1920058) | Cod sursa (job #2682065) | Cod sursa (job #573799)
Cod sursa(job #573799)
#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;
struct ceva
{
double y1;
double y2;
}dreapta[200100],stanga[200100],liniStanga[200100],liniDreapta[200100];
int n;
int istanga;
int idreapta;
int s;
bool cmp(ceva x, ceva y)
{
if(x.y1>y.y1)
return true;
return false;
}
void citire()
{
scanf("%d",&n);
for(int i=0;i<n;++i)
{
int x;
int y1;
int y2;
scanf("%d %d %d",&x,&y1,&y2);
if(y2>y1)
{
int aux=y2;
y2=y1;
y1=aux;
}
if(x>0)
{
if(y1==0)
dreapta[idreapta].y1=1;
else
if(y1>0)
{
dreapta[idreapta].y1=1+atan((double)y1/x);
}
else
{
y1*=-1;
dreapta[idreapta].y1=atan((double)x/y1);
}
/////////////////
if(y2==0)
dreapta[idreapta].y2=1;
else
if(y2>0)
{
dreapta[idreapta].y2=1+atan((double)y2/x);
}
else
{
y2*=-1;
dreapta[idreapta].y2=atan((double)x/y2);
}
idreapta++;
}
else
{
x*=-1;
if(y1==0)
stanga[istanga].y1=1;
else
if(y1>0)
{
stanga[istanga].y1=1+atan((double)y1/x);
}
else
{
y1*=-1;
stanga[istanga].y1=atan((double)x/y1);
}
/////////////////////
if(y2==0)
stanga[istanga].y2=1;
else
if(y2>0)
{
stanga[istanga].y2=1+atan((double)y2/x);
}
else
{
y2*=-1;
stanga[istanga].y2=atan((double)x/y2);
}
istanga++;
}
}
}
void verf(ceva x,ceva linii[], int &m)
{
for(int i=0;i<m;i++)
{
if(x.y1<=linii[i].y1 && x.y2>=linii[i].y2)
{
linii[i].y1=x.y1;
linii[i].y2=x.y2;
return;
}
else
if(x.y2>=linii[i].y2 && x.y2<=linii[i].y1)
{
linii[i].y2=x.y2;
return;
}
else
if(x.y1<=linii[i].y1 && x.y1>=linii[i].y2)
{
linii[i].y1=x.y1;
return;
}
else
if(linii[i].y1<=x.y1 && linii[i].y2>=x.y2)
{
return;
}
}
linii[m].y1=x.y1;
linii[m++].y2=x.y2;
s++;
return;
}
void linii(ceva unghiuri[],ceva linii[],int n)
{
int m=0; // lungime linii;
for(int i=0;i<n;i++)
{
verf(unghiuri[i],linii,m);
}
}
int main()
{
freopen("rays.in","r",stdin);
freopen("rays.out","w",stdout);
citire();
sort(dreapta,dreapta+idreapta,cmp);
sort(stanga,stanga+istanga,cmp);
linii(dreapta,liniDreapta,idreapta);
linii(stanga,liniStanga,istanga);
printf("%d\n",s);
return 0;
}