Pagini recente » Istoria paginii runda/hmmmm/clasament | Istoria paginii runda/oni_11_12_8/clasament | Monitorul de evaluare | Istoria paginii runda/iuiui/clasament | Cod sursa (job #2017533)
# include <fstream>
# include <algorithm>
# define DIM 400010
# define a first.first
# define b first.second
# define c second
using namespace std;
ifstream fin("rays.in");
ofstream fout("rays.out");
pair<pair<int,int>,int> v[DIM];
int Marcat[DIM],s[DIM],n,x,y,z,i,j,k,u,nr;
int cadran(int x,int y){
if(x>0&&y<0)
return 1;
if(x>0&&y>=0)
return 2;
if(x<0&&y>=0)
return 3;
return 4;
}
bool cmp(pair<pair<int,int>,int> x,pair<pair<int,int>,int> y){
if(cadran(x.a,x.b)==cadran(y.a,y.b)){
if(1LL*x.a*y.b==1LL*x.b*y.a)
return x.c<y.c;
return 1LL*x.a*y.b>1LL*x.b*y.a;
}
return cadran(x.a,x.b)<cadran(y.a,y.b);
}
int main () {
fin>>n;
for(i=1;i<=n;i++){
fin>>x>>y>>z;
if(x>0&&y>z)
swap(y,z);
if(x<0&&y<z)
swap(y,z);
v[++k].a=x;
v[k].b=y;
v[k].c=-i;
v[++k].a=x;
v[k].b=z;
v[k].c=i;
}
sort(v+1,v+k+1,cmp);
for(i=1;i<=k;i++){
if(v[i].c<0||(v[i].c>0&&Marcat[v[i].c]==1))
s[++u]=-v[i].c;
else{
nr++;
for(j=1;j<=u;j++)
Marcat[s[j]]=1;
u=0;
}
}
fout<<nr<<"\n";
return 0;
}