Pagini recente » Cod sursa (job #2375897) | Cod sursa (job #707967) | Cod sursa (job #2114239) | Cod sursa (job #1783418) | Cod sursa (job #197002)
Cod sursa(job #197002)
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MP make_pair
#define ff first
#define ss second
#define NMAX 200010
int N;
const double pi = acos(-1);
vector <pair <double, pair<int, int> > > ev;
vector <int> cur;
char scos[NMAX];
double get_unghi(int x, int y)
{
double unghi = atan2(y, x);
if (unghi < 0) unghi += 2 * pi;
if (unghi > 3 * pi * 0.5) unghi -= 2 * pi;
return unghi;
}
int main()
{
int i, x, y1, y2;
double u1, u2;
freopen("rays.in", "r", stdin);
freopen("rays.out", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; i++) {
scanf("%d %d %d", &x, &y1, &y2);
u1 = get_unghi(x, y1);
u2 = get_unghi(x, y2);
if (u1 > u2) swap(u1, u2);
ev.push_back(MP(u1, MP(i,-1)));
ev.push_back(MP(u2, MP(i, 1)));
}
sort(ev.begin(), ev.end());
int nev = ev.size(), rez = 0;
for (i = 0; i < nev; i++) {
if (ev[i].ss.ss == -1) cur.push_back(ev[i].ss.ff);
else {
if (scos[ev[i].ss.ff]) continue;
for (vector <int> :: iterator it = cur.begin(); it != cur.end(); ++it) scos[*it] = 1;
cur.clear();
rez++;
}
}
printf("%d\n", rez);
return 0;
}