Pagini recente » Cod sursa (job #888070) | Cod sursa (job #2263515) | Cod sursa (job #1655400) | Cod sursa (job #1235427) | Cod sursa (job #196731)
Cod sursa(job #196731)
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int n, rez, n1, n2;
typedef struct
{
double x, y;
} interval;
interval a[200005], b[200005], c[200005];
void swap(int &x, int &y)
{
int t = x; x = y; y = t;
}
void bublesort(int x)
{
int i, ok = 1;
interval aux;
while (ok)
{
ok = 0;
for (i = 1; i < x; i++)
if (c[i].x < c[i-1].x)
{
aux = c[i];
c[i] = c[i -1];
c[i - 1] = aux;
ok = 1;
}
}
}
bool operator<(const interval &x, const interval &y)
{
return x.x < y.x;
}
int main()
{
freopen("rays.in","r",stdin);
freopen("rays.out","w",stdout);
int i, x, y1, y2;
scanf("%d",&n);
for (i = 1; i <= n; i++)
{
scanf("%d %d %d",&x,&y1,&y2);
if (y1 > y2) swap(y1,y2);
if (x > 0)
{
a[n1].x = (double) y1 / x;
a[n1].y = (double) y2 / x;
n1++;
}
else
{
x *= (-1);
b[n2].x = (double) y1 / x;
b[n2].y = (double) y2 / x;
n2++;
}
}
for (i = 0; i < n1; i++) c[i] = a[i];
std::sort(c, c+n1);
double xx;
xx = c[0].y;
for (i = 1; i < n1; i++)
{
if (c[i].x > xx)
{
rez++;
xx = c[i].y;
}
else if (c[i].y < xx) xx = c[i].y;
}
rez++;
for (i = 0; i < n2; i++) c[i] = b[i];
std::sort(c, c+n2);
xx = c[0].y;
for (i = 1; i < n2; i++)
{
if (c[i].x > xx)
{
rez++;
xx = c[i].y;
}
else if (c[i].y < xx) xx = c[i].y;
}
rez++;
printf("%d\n",rez);
return 0;
}