Pagini recente » Cod sursa (job #614649) | Cod sursa (job #114873) | Cod sursa (job #2311010) | Cod sursa (job #769526) | Cod sursa (job #2207521)
#include <cstdio>
#include <algorithm>
using namespace std;
struct segm{
int a;
int o;
int tip;
int poz;
};
segm v[400001];
int f[200001],cdr[200001];
int cmp (segm x,segm y){
if (cdr[x.poz]!=cdr[y.poz])
return cdr[x.poz]<cdr[y.poz];
if ((1LL*x.o*y.a) == (1LL*x.a * y.o))
return x.tip>y.tip;
if (cdr[x.poz]==1)
return (1LL*x.o*y.a) < (1LL*x.a * y.o);
return (1LL*x.o*y.a) > (1LL*x.a * y.o);
}
int main()
{
FILE *fin=fopen ("rays.in","r");
FILE *fout=fopen ("rays.out","w");
int n,s,elim,sol,i;
int x,y1,y2;
fscanf (fin,"%d",&n);
s=0;
for (i=1;i<=n;i++){
fscanf (fin,"%d%d%d",&x,&y1,&y2);
if (x<0)
cdr[i]=2;
else cdr[i]=1;
v[++s].a=x;
v[s].o=min(y1,y2);
v[s].tip=1; // incepe un segment
v[s].poz=i;
v[++s].a=x;
v[s].o=max(y1,y2);
v[s].tip=0; // se termina un segment
v[s].poz=i;
}
// este gresit sa incerc sa normalizez
sort (v+1,v+s+1,cmp); // am sortat dupa unghiul cu ox
sol=0;
elim=0;
for (i=1;i<=s;i++){
if (v[i].tip==1) // eveniment 1 : incepe un segment
f[v[i].poz]=i;
else {// eveniment 2 : se termina un segment
if (f[v[i].poz]>elim){ // daca nu l am anulat cu alta ocazie
sol++;
elim=i;
}
}
}
fprintf (fout,"%d",sol);
return 0;
}