Pagini recente » Cod sursa (job #1966033) | Cod sursa (job #2754644) | Cod sursa (job #2854700) | Cod sursa (job #190760) | Cod sursa (job #2244827)
#include <fstream>
#include <cstdio>
#include <map>
#include <queue>
#include <cmath>
#include <algorithm>
#define VAL 200005
#define PI 3.14159265
using namespace std;
int N, M, i, j, A, B, K, st[VAL], top;
int X[VAL], Y1[VAL], Y2[VAL], ANS;
double P[2*VAL], Angle;
bool ok[VAL];
map < double, int > H;
struct eveniment
{
int nr, inter;
char semn;
};
eveniment EV[2*VAL];
void Unghi(double &U, int X, int Y)
{
U=atan2(Y, X)*180 / PI;
U+=90;
if (U>=360)
U-=360;
}
bool cmp(eveniment A, eveniment B)
{
if (A.nr!=B.nr)
return A.nr<B.nr;
if (A.semn=='+')
return true;
return false;
}
int main()
{
freopen("rays.in", "r", stdin);
freopen("rays.out", "w", stdout);
scanf("%d", &N);
for (i=1; i<=N; i++)
{
scanf("%d %d %d", &X[i], &Y1[i], &Y2[i]);
M++;
Unghi(P[M], X[i], Y1[i]);
M++;
Unghi(P[M], X[i], Y2[i]);
}
sort(P+1, P+M+1);
for (i=1; i<=M; i++)
{
if (P[i]!=P[i-1])
{
K++;
H[P[i]]=K;
}
}
M=0;
for (i=1; i<=N; i++)
{
Unghi(Angle, X[i], Y1[i]);
A=H[Angle];
Unghi(Angle, X[i], Y2[i]);
B=H[Angle];
if (A>B)
swap(A, B);
EV[++M].nr=A;
EV[M].semn='+';
EV[M].inter=i;
EV[++M].nr=B;
EV[M].semn='-';
EV[M].inter=i;
}
sort(EV+1, EV+M+1, cmp);
for (i=1; i<=M; i++)
{
if (EV[i].semn=='+')
st[++top]=EV[i].inter;
else
{
if (ok[EV[i].inter]==false)
{
ANS++;
while (top>0)
{
ok[st[top]]=true;
top--;
}
}
}
}
printf("%d\n", ANS);
return 0;
}