Pagini recente » Cod sursa (job #1322861) | Cod sursa (job #1853578) | Cod sursa (job #2561326) | Cod sursa (job #886430) | Cod sursa (job #2207368)
#include <cstdio>
#include <algorithm>
using namespace std;
struct segm{
int a;
int o;
int tip;
int poz;
};
segm v[200001];
int f[200001];
int cadran (segm x){
if (x.a<0)
return 2;
return 1;
}
pair <int,int> tan (segm x){
return make_pair( x.o , x.a );
}
int cmp (segm x,segm y){
pair <long long,long long> xx,yy;
xx=tan(x);
yy=tan(y);
if (cadran(x)!=cadran(y))
return cadran(x)<cadran(y);
if ((xx.first*yy.second) != (xx.second * yy.first) && cadran(x)==1)
return (xx.first*yy.second) < (xx.second * yy.first);
else if ((xx.first*yy.second) != (xx.second * yy.first) && cadran(x)==2)
return (xx.first*yy.second) > (xx.second * yy.first);
return x.tip>y.tip;
}
int main()
{
FILE *fin=fopen ("rays.in","r");
FILE *fout=fopen ("rays.out","w");
int n,s,x,y1,y2,mini,l,elim,sol,i;
fscanf (fin,"%d",&n);
s=0;
for (i=1;i<=n;i++){
fscanf (fin,"%d%d%d",&x,&y1,&y2);
mini=min(mini,min (y1,y2));
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
l=0;
sol=0;
elim=0;
//printf ("%d ",cmp (v[3],v[4]));
for (i=1;i<=s;i++){
//if (i==9)
// printf ("a");
//printf ("%d %d\n",v[i].a,v[i].o);
if (v[i].tip==1){
l++; // 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+=v[i].poz;
l=0;
}
}
}
fprintf (fout,"%d",sol);
return 0;
}