Pagini recente » Statistici Ungureanu Mihnea Dragos (Mi_igrec) | Cod sursa (job #413633) | Monitorul de evaluare | Cod sursa (job #2956031) | Cod sursa (job #113368)
Cod sursa(job #113368)
Utilizator |
Andrei Grigorean wefgef |
Data |
9 decembrie 2007 19:05:00 |
Problema |
Rays |
Scor |
Ascuns |
Compilator |
cpp |
Status |
done |
Runda |
|
Marime |
1.1 kb |
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define sz(c) int((c).size())
#define all(c) (c).begin(), (c).end()
typedef struct Segment {
int x, y1, y2;
} Segment;
int ret;
vector<Segment> v, u;
void ReadData() {
freopen("rays.in", "r", stdin);
freopen("rays.out", "w", stdout);
int N;
for (scanf("%d", &N); N; --N) {
Segment tmp;
scanf("%d %d %d", &tmp.x, &tmp.y1, &tmp.y2);
if (tmp.y1 > tmp.y2) tmp.y1 ^= tmp.y2 ^= tmp.y1 ^= tmp.y2;
if (tmp.x > 0) v.pb(tmp);
else {
tmp.x *= -1;
u.pb(tmp);
}
}
}
int cross(int X1, int Y1, int X2, int Y2) {
long long P = (long long)X1*Y2 - (long long)X2*Y1;
if (P == 0) return 0;
return P > 0 ? 1 : -1;
}
inline int cmp(Segment a, Segment b) {
return cross(a.x, a.y2, b.x, b.y2) == 1;
}
void Solve(vector<Segment> &v) {
sort(all(v), cmp);
if (!sz(v)) return;
int X = v[0].x;
int Y = v[0].y2;
++ret;
for (int i = 1; i < sz(v); ++i)
if (cross(X, Y, v[i].x, v[i].y1) == 1) {
++ret;
X = v[i].x;
Y = v[i].y2;
}
}
int main() {
ReadData();
Solve(v);
Solve(u);
printf("%d\n", ret);
}