Pagini recente » Cod sursa (job #2311776) | Cod sursa (job #310677) | Cod sursa (job #3206287) | Cod sursa (job #800611) | Cod sursa (job #644285)
Cod sursa(job #644285)
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define EPS 0.000000001
#define PI 3.1415926535
#define LMAX 200100
using namespace std;
struct point
{
int x, y, line;
} x[2 * LMAX];
bool events[LMAX], used[LMAX];
int st[2 * LMAX];
double unghi (point A) //unghiul OA in radiani
{
double panta = (double)A.y / A.x, alfa = atan (panta);
if (A.x > 0 && A.y > 0)
return alfa;
if (A.x < 0 && A.y >= 0)
return PI - alfa;
if (A.x < 0 && A.y < 0)
return PI + alfa;
return 2 * PI - alfa;
}
inline bool comp (point A, point B)
{
return unghi (A) - unghi (B) <= EPS * (-1);
}
int main ()
{
int i, N, x0, y1, y2, lenth = 0, sol = 0;
freopen ("rays.in", "r", stdin);
freopen ("rays.out", "w", stdout);
scanf ("%d", &N);
for (i = 1; i <= N; i ++)
{
scanf ("%d%d%d", &x0, &y1, &y2);
x[++ lenth].x = x0; x[lenth].y = y1; x[lenth].line = i;
x[++ lenth].x = x0; x[lenth].y = y2; x[lenth].line = i;
}
sort (x + 1, x + 2 * N + 1, comp); //Sortez punctele in functie de unghiul facut cu OX
lenth = 0;
for (i = 1; i <= N + N; i ++)
if (!used[x[i].line])
if (!events[x[i].line])
st[++ lenth] = x[i].line, events[x[i].line] = true;
else
{
sol ++;
while (st[lenth] != x[i].line)
used[st[lenth --]] = 1;
used[st[lenth --]] = 1;
}
printf ("%d", sol);
return 0;
}