Pagini recente » Cod sursa (job #1921477) | Cod sursa (job #3124811) | Cod sursa (job #483888) | Cod sursa (job #439091) | Cod sursa (job #2749526)
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream in("rays.in");
ofstream out("rays.out");
const int nmax=2e5+10;
const int inf=1e9+10;
const double eps=1.0e-14;
struct interval
{
float inc,fin;
} v[nmax],s[nmax];
bool cmp(interval a,interval b)
{
if(a.inc==b.inc)
return a.fin<b.fin;
return a.inc<b.inc;
}
int main()
{
int n,i,k,ok,j,ck,c=0;
float x,y1,y2;
///cadranul 1 si 4(x pozitiv)
in>>n;
for(i=1; i<=n; i++)
{
in>>x>>y1>>y2;
if(x<0)
continue;
if(y1>y2)
swap(y1,y2);
v[++c].inc=y1/x;
v[c].fin=y2/x;
}
in.close();
sort(v+1,v+c+1,cmp);
s[1].inc=v[1].inc;
s[1].fin=v[1].fin;
k=1;
for(i=2; i<=c; i++)
{
ok=0;
for(j=1; j<=k && !ok; j++)
{
if((v[i].inc<=s[j].inc && s[j].inc<=v[i].fin)||(s[j].inc<=v[i].inc && v[i].inc<=s[j].fin)||(s[j].inc<=v[i].inc && v[i].fin<=s[j].fin))
{
ok=1;
s[j].inc=max(s[j].inc,v[i].inc);
s[j].fin=min(s[j].fin,v[i].fin);
}
}
if(!ok)
{
s[++k].inc=v[i].inc;
s[k].fin=v[i].fin;
}
}
ck=k;
///cadranul 2 si 3 (x negativ)
ifstream in1("rays.in");
c=0;
in1>>n;
for(i=1; i<=n; i++)
{
in1>>x>>y1>>y2;
if(x>0)
continue;
x*=-1;
if(y1>y2)
swap(y1,y2);
v[++c].inc=y1/x;
v[c].fin=y2/x;
}
in1.close();
sort(v+1,v+c+1,cmp);
s[1].inc=v[1].inc;
s[1].fin=v[1].fin;
k=1;
for(i=2; i<=c; i++)
{
ok=0;
for(j=1; j<=k && !ok; j++)
{
if((v[i].inc<=s[j].inc && s[j].inc<=v[i].fin)||(s[j].inc<=v[i].inc && v[i].inc<=s[j].fin)||(s[j].inc<=v[i].inc && v[i].fin<=s[j].fin))
{
ok=1;
s[j].inc=max(s[j].inc,v[i].inc);
s[j].fin=min(s[j].fin,v[i].fin);
}
}
if(!ok)
{
s[++k].inc=v[i].inc;
s[k].fin=v[i].fin;
}
}
k+=ck;
out<<k;
return 0;
}