Pagini recente » Cod sursa (job #2706541) | Cod sursa (job #1937575) | Cod sursa (job #1385709) | Cod sursa (job #1188994) | Cod sursa (job #2207528)
#include <cstdio>
#include <algorithm>
using namespace std;
struct segm{
double tan;
int tip;
int poz;
};
segm st[400001],dr[400001];
int f[200001];
inline double modul (double x){
if (x>=1.0 * 0)
return x;
return -x;
}
inline int cmp (segm x,segm y){
if (modul(x.tan-y.tan)<(double)0.0000001)
return x.tip>y.tip;
return x.tan<y.tan;
}
int main()
{
FILE *fin=fopen ("rays.in","r");
FILE *fout=fopen ("rays.out","w");
int n,elim,sol,i,ss,sd;
int x,y1,y2;
fscanf (fin,"%d",&n);
ss=sd=0;
for (i=1;i<=n;i++){
fscanf (fin,"%d%d%d",&x,&y1,&y2);
if (y1>y2)
swap(y1,y2);
if (x<0){
st[++ss].tan=-(1.0*y1)/x;
st[ss].tip=1; // incepe un segment
st[ss].poz=i;
st[++ss].tan=-(1.0*y2)/x;
st[ss].tip=0; // se termina un segment
st[ss].poz=i;
}
else{
dr[++sd].tan=(1.0*y1)/x;
dr[sd].tip=1; // incepe un segment
dr[sd].poz=i;
dr[++sd].tan=(1.0*y2)/x;
dr[sd].tip=0; // se termina un segment
dr[sd].poz=i;
}
}
// este gresit sa incerc sa normalizez
sort (st+1,st+ss+1,cmp); // am sortat dupa unghiul cu ox
sort (dr+1,dr+sd+1,cmp);
sol=0;
elim=0;
for (i=1;i<=ss;i++){
if (st[i].tip==1) // eveniment 1 : incepe un segment
f[st[i].poz]=i;
else {// eveniment 2 : se termina un segment
if (f[st[i].poz]>elim){ // daca nu l am anulat cu alta ocazie
sol++;
elim=i;
}
}
}
elim=0;
for (i=1;i<=sd;i++){
if (dr[i].tip==1) // eveniment 1 : incepe un segment
f[dr[i].poz]=i;
else {// eveniment 2 : se termina un segment
if (f[dr[i].poz]>elim){ // daca nu l am anulat cu alta ocazie
sol++;
elim=i;
}
}
}
fprintf (fout,"%d",sol);
return 0;
}