Pagini recente » Cod sursa (job #1398827) | Cod sursa (job #322654) | Cod sursa (job #1327267) | Cod sursa (job #2727997) | Cod sursa (job #2447722)
#include<fstream>
#include<iomanip>
#include<iostream>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,dim;
double panta,pmin,pmax;
struct punct
{
double x;
double y;
};
punct e[120005],infasuratoare[120005],P,Q,minn,maxx,P1,P2,P3,P4;
int main()
{
f>>n;
for(i=1;i<=n;i++)
f>>e[i].x>>e[i].y;
P1.x=2147348646;
P2.x=-2147348646;
P3.x=-2147348646;
P4.x=2147348646;
P1.y=2147348646;
P2.y=2147348646;
P3.y=-2147348646;
P4.y=-2147348646;
dim=0;
for(i=1;i<=n;i++)
{
if(e[i].x<P4.x)
P4=e[i];
if(e[i].x>P2.x)
P2=e[i];
if(e[i].y<P1.y)
P1=e[i];
if(e[i].y>P3.y)
P3=e[i];
}
for(i=1;i<=n;i++)
{
if(e[i].x==P4.x)
if(e[i].y>P4.y)
P4=e[i];
if(e[i].x==P2.x)
if(e[i].y<P2.y)
P2=e[i];
if(e[i].y==P1.y)
if(e[i].x<P1.x)
P1=e[i];
if(e[i].y==P3.y)
if(e[i].x>P3.x)
P3=e[i];
}
///cout<<P1.x<<" "<<P1.y<<"\n";
///cout<<P2.x<<" "<<P2.y<<"\n";
///cout<<P3.x<<" "<<P3.y<<"\n";
///cout<<P4.x<<" "<<P4.y<<"\n";
dim++;
infasuratoare[dim]=P1;
P=P1;
while(! (P.x==P2.x && P.y==P2.y))
{
pmin=2147348646;
panta=0;
for(i=1;i<=n;i++)
{
if(e[i].x>P.x)
{
Q=e[i];
///verificam daca punctul Q este cel cautat
///calculam panta
panta=(Q.y-P.y)/(Q.x-P.x);
if(panta<=pmin)
{
pmin=panta;
minn=Q;
}
}
}
P=minn;
dim++;
infasuratoare[dim]=P;
///cout<<P.x<<" "<<P.y<<"\n";
}
while(! (P.x==P3.x && P.y==P3.y))
{
pmax=-2147348646;
panta=0;
for(i=1;i<=n;i++)
{
if(e[i].y>P.y)
{
Q=e[i];
///verificam daca punctul Q este cel cautat
///calculam panta
if(Q.x-P.x==0)
panta=0;
else
panta=(Q.y-P.y)/(Q.x-P.x);
if(panta>=pmax)
{
pmax=panta;
maxx=Q;
}
}
}
P=maxx;
dim++;
infasuratoare[dim]=P;
///cout<<P.x<<" "<<P.y<<"\n";
}
while(! (P.x==P4.x && P.y==P4.y))
{
pmin=2147348646;
panta=0;
for(i=1;i<=n;i++)
{
if(e[i].x<P.x)
{
Q=e[i];
///verificam daca punctul Q este cel cautat
///calculam panta
panta=(Q.y-P.y)/(Q.x-P.x);
if(panta<=pmin)
{
pmin=panta;
minn=Q;
}
}
}
P=minn;
dim++;
infasuratoare[dim]=P;
///cout<<P.x<<" "<<P.y<<"\n";
}
while(! (P.x==P1.x && P.y==P1.y))
{
pmax=-2147348646;
panta=0;
for(i=1;i<=n;i++)
{
if(e[i].y<P.y)
{
Q=e[i];
///verificam daca punctul Q este cel cautat
///calculam panta
if(Q.x-P.x==0)
panta=0;
else
panta=(Q.y-P.y)/(Q.x-P.x);
if(panta>=pmax)
{
pmax=panta;
maxx=Q;
}
}
}
P=maxx;
dim++;
infasuratoare[dim]=P;
///cout<<P.x<<" "<<P.y<<"\n";
}
infasuratoare[dim].x=0;
infasuratoare[dim].y=0;
dim--;
g<<dim<<"\n";
for(i=1;i<=dim;i++)
{
g<<fixed<<setprecision(6)<<infasuratoare[i].x<<" ";
g<<fixed<<setprecision(6)<<infasuratoare[i].y<<"\n";
}
f.close();
g.close();
return 0;
}