Pagini recente » Monitorul de evaluare | Cod sursa (job #657262) | Cod sursa (job #1471097) | Cod sursa (job #2687597) | Cod sursa (job #753887)
Cod sursa(job #753887)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
ofstream out("rays.out");
struct dreapta {int x,y1,y2;};
int n,lst,ldr,sol;
pair<double,double> st[200100],dr[200100];
dreapta a[200100];
struct cmp
{
bool operator()(const pair<double,double> &a,const pair<double,double> &b)const
{
if(a.first==b.first)
{
return a.second<b.second;
}
return a.first<b.first;
}
};
inline int make(pair<double,double> a[],int lung)
{
int ret=0;
sort(a+1,a+lung+1,cmp());
for(int i=1;i<=lung;++i)
{
//cout<<a[i].first<<' '<<a[i].second<<'\n';
}
cout<<'\n';
pair<double,double> var;
var=a[1];
a[lung+1]=make_pair(2000000000,2000000000);
for(int i=2;i<=lung+1;++i)
{
//cout<<var.first<<" "<<var.second<<" "<<a[i].first<<" "<<a[i].second<<"\n";
//cout<<max(var.first,a[i].first)<<" "<<min(var.second,a[i].second)<<"\n";
if(max(var.first,a[i].first)<=min(var.second,a[i].second))
{
var.first=max(var.first,a[i].first);
var.second=min(var.second,a[i].second);
}
else
{
//cout<<var.first<<" "<<var.second<<" "<<a[i].first<<" "<<a[i].second<<"\n";
//exit(0);
var=a[i];
++ret;
}
}
return ret;
}
int main()
{
ifstream in("rays.in");
in>>n;
for(int i=1;i<=n;++i)
{
in>>a[i].x>>a[i].y1>>a[i].y2;
if(a[i].x<0)
{
++lst;
st[lst].first=1.0*a[i].y1/a[i].x;
st[lst].second=1.0*a[i].y2/a[i].x;
if(st[lst].first>st[lst].second) swap(st[lst].first,st[lst].second);
}
else
{
++ldr;
dr[ldr].first=1.0*a[i].y1/a[i].x;
dr[ldr].second=1.0*a[i].y2/a[i].x;
if(dr[ldr].first>dr[ldr].second) swap(dr[ldr].first,dr[ldr].second);
}
}
sol=make(st,lst)+make(dr,ldr);
out<<sol<<'\n';
out.close();
return 0;
}