Pagini recente » Cod sursa (job #378107) | Cod sursa (job #113621)
Cod sursa(job #113621)
Utilizator |
Airinei Adrian astronomy |
Data |
10 decembrie 2007 21:51:09 |
Problema |
Rays |
Scor |
Ascuns |
Compilator |
cpp |
Status |
done |
Runda |
|
Marime |
1.45 kb |
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define PII pair<double, short int>
#define XINF 2000000001
#define NMax 200005
#define EPS 1e-4
#define ll long long
#define x first
#define y second
int N, X[NMax], Y1[NMax], Y2[NMax], bst;
PII S[NMax<<1];
int cmp(double a, double b)
{
if (fabs(a-b) < EPS) return 0;
if (a > b) return +1;
return -1;
}
int cmp_pair(const PII& a, const PII& b)
{
int ok = cmp(a.x, b.x);
if (ok)
return ok == -1;
return a.y > b.y;
}
int solve(int sg)
{
int i, h = 0, cnt = 0, ql = 0;
for (i = 1; i <= N; i++)
if (X[i] * sg > 0)
{
X[i] *= sg;
++h, S[h].x = ((double)Y1[i] / X[i]) * XINF, S[h].y = +1;
++h, S[h].x = ((double)Y2[i] / X[i]) * XINF, S[h].y = -1;
}
sort(S+1, S+h+1, cmp_pair);
for (i = 1, ql = 0; i <= h+1; i++)
if (S[i].y == +1)
ql++;
else
cnt += (ql != 0), ql = 0;
return cnt;
}
int main(void)
{
int i, aux;
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]);
if (Y1[i] > Y2[i])
aux = Y1[i], Y1[i] = Y2[i], Y2[i] = aux;
}
bst = solve(1) + solve(-1);
printf("%d\n", bst);
return 0;
}