Pagini recente » Cod sursa (job #2392774) | Cod sursa (job #234778) | Cod sursa (job #1463008) | Cod sursa (job #1345670) | Cod sursa (job #36180)
Cod sursa(job #36180)
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
//constanta care determina daca sorteaza invers
int inv=1;
struct punct
{
long x;
long y;
};
inline int comp(punct p1,punct p2)
{
if (inv==0)
{
return p1.y<p2.y;
}
else
{
return p1.y>p2.y;
}
}
int main(void)
{
FILE *f;
vector< punct > v1;
vector< punct > v2;
vector< punct > v3;
vector< punct > v4;
unsigned int i,j,n;
long int x,y;
long int x0,y0;
punct p;
unsigned int drumuri=0;
vector<bool> s1;
vector<bool> s2;
vector<bool> s3;
vector<bool> s4;
unsigned int n1,n2,n3,n4;
//citeste datele de intrare si separa pe cadrane
f=fopen("pachete.in","rt");
fscanf(f,"%d",&n);
fscanf(f,"%ld %ld",&x0,&y0);
for(i=0;i<n;i++)
{
fscanf(f,"%ld %ld",&x,&y);
p.x=x;
p.y=y;
if((x>x0)&&(y>y0))
{
v1.push_back(p);
s1.push_back(false);
}
if((x>x0)&&(y<y0))
{
v2.push_back(p);
s2.push_back(false);
}
if((x<x0)&&(y<y0))
{
v3.push_back(p);
s3.push_back(false);
}
if((x<x0)&&(y>y0))
{
v4.push_back(p);
s4.push_back(false);
}
}
fclose(f);
//sortaeaza punctele in cadran dupa y
//sorteaza pe 1 si 4 cu normal
inv=0;
stable_sort(v1.begin(),v1.end(),comp);
stable_sort(v4.begin(),v4.end(),comp);
inv=1;
stable_sort(v2.begin(),v2.end(),comp);
stable_sort(v3.begin(),v3.end(),comp);
//face numarul de drumuri din fiecare cadran
n1=v1.size();
n2=v2.size();
n3=v3.size();
n4=v4.size();
//face numarul de drumuri din cadranul 1
while(n1>0)
{
i=0;
while((s1[i]==true)&&(i<v1.size()))
i++;
j=i;
while(i<v1.size())
{
if((s1[i]==false)&&(v1[i].x>=v1[j].x))
{
s1[i]=true;
n1-=1;
j=i;
}
i++;
}
drumuri+=1;
}
//face numarul de drumuri din cadranul 2
while(n2>0)
{
i=0;
while((s2[i]==true)&&(i<v2.size()))
i++;
j=i;
while(i<v2.size())
{
if((s2[i]==false)&&(v2[i].x>=v2[j].x))
{
s2[i]=true;
n2-=1;
j=i;
}
i++;
}
drumuri+=1;
}
//face numarul de drumuri din cadranul 3
while(n3>0)
{
i=0;
while((s3[i]==true)&&(i<v3.size()))
i++;
j=i;
while(i<v3.size())
{
if((s3[i]==false)&&(v3[i].x<=v3[j].x))
{
s3[i]=true;
n3-=1;
j=i;
}
i++;
}
drumuri+=1;
}
//face numarul de drumuri din cadranul 3
while(n4>0)
{
i=0;
while((s4[i]==true)&&(i<v4.size()))
i++;
j=i;
while(i<v4.size())
{
if((s4[i]==false)&&(v4[i].x<=v4[j].x))
{
s4[i]=true;
n4-=1;
j=i;
}
i++;
}
drumuri+=1;
}
//afiseaza
f=fopen("pachete.out","wt");
fprintf(f,"%u\n",drumuri);
fclose(f);
//sf
return 0;
};