Pagini recente » Cod sursa (job #105159) | Cod sursa (job #2172576) | Cod sursa (job #1653826) | Cod sursa (job #1286300) | Cod sursa (job #1754225)
#include<fstream>
#include<algorithm>
#include<cstring>
#define DIM 400005
using namespace std;
int n, i, a, b, c, sol, nrs, nrd;
int cd[DIM], f[DIM / 2];
struct str{
int x;
int y;
int t;
int ii;
};
str v[2][DIM];
ifstream fin("rays.in");
ofstream fout("rays.out");
int cadran(int x, int y){
if(y >= 0){
return 0;
}
return 1;
}
long long det(int X1, int Y1, int X2, int Y2){
return X1 * 1LL * Y2 - X2 * 1LL * Y1;
}
long long dist(int x, int y){
return x * 1LL * x + y * 1LL * y;
}
int cmp(str a, str b){
int c1 = cadran(a.x, a.y);
int c2 = cadran(b.x, b.y);
if(c1 != c2){
return c1 < c2;
}
long long d = det(a.x, a.y, b.x, b.y);
if(d != 0){
return d > 0;
}
return dist(a.x, a.y) < dist(b.x, b.y);
}
void ff(int tt, int nr){
int u = 0, i;
nr *= 2;
memset(f, 0, sizeof(f));
sort(v[tt] + 1, v[tt] + nr + 1, cmp);
for(i = 1; i <= nr; i++){
if(v[tt][i].t == 0){
u++;
cd[u] = v[tt][i].ii;
}
else{
if(f[ v[tt][i].ii ] == 0){
sol++;
while(u > 0){
f[ cd[u] ] = 1;
u--;
}
}
}
}
}
int main(){
fin>> n;
for(i = 1; i <= n; i++){
fin>> a >> b >> c;
if(b > c){
swap(b, c);
}
if(a < 0){
nrs++;
v[0][2 * nrs - 1].x = v[0][2 * nrs].x = -a;
v[0][2 * nrs - 1].ii = v[0][2 * nrs].ii = i;
v[0][2 * nrs - 1].y = b;
v[0][2 * nrs].y = c;
v[0][2 * nrs - 1].t = 0;
v[0][2 * nrs].t = 1;
}
else{
nrd++;
v[1][2 * nrs - 1].x = v[0][2 * nrs].x = a;
v[1][2 * nrs - 1].ii = v[0][2 * nrs].ii = i;
v[1][2 * nrs - 1].y = b;
v[1][2 * nrs].y = c;
v[1][2 * nrs - 1].t = 0;
v[1][2 * nrs].t = 1;
}
}
ff(0, nrs);
ff(1, nrd);
fout<< sol <<"\n";
return 0;
}