Pagini recente » Cod sursa (job #62577) | Borderou de evaluare (job #2394031) | Cod sursa (job #2635626)
#include <fstream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <iomanip>
#include <limits>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
double ax,ay;
int n,k,i,j,bur;
double a;
struct adat
{
double x,y,s;
};
vector<adat>x;
int has(adat a, adat b)
{
if(a.s<b.s) return 1;
else if(a.s==b.s && (a.x-ax)<(b.x-ax)) return 1;
else return 0;
}
int fgv(double qx,double qy,double rx,double ry,double px,double py)
{
int f=0;
double cr=(rx-qx)*(py-qy)-(px-qx)*(ry-qy);
if(cr<0) f=-1;
else if(cr>0) f=1;
else f=0;
return f;
}
int main()
{
cin>>n;
x.resize(n+1);
x[0].s=-5;
ax=0;
ay=INT_MAX;
for(i=1;i<=n;i++)
{
cin>>x[i].x>>x[i].y;
if(x[i].y<ay)
{
ay=x[i].y;
ax=x[i].x;
}
else if(x[i].y==ay && x[i].x<ax)
{
ax=x[i].x;
ay=x[i].y;
}
}
for(i=1;i<=n;++i)
{
if(x[i].x==ax && x[i].y==ay) x[i].s=-1;
else if(x[i].x==ax) x[i].s=90;
else
{
a=0;
a=(double)(x[i].y-ay)/(x[i].x-ax);
x[i].s=(double)atan(a)/3.14159265*180;
if(x[i].s<0)
x[i].s+=180;
}
}
sort(x.begin(),x.end(),has);
x.push_back({ax,ay,-1});
vector<adat>v;
v.resize(n+5);
v[1].x=ax;
v[1].y=ay;
v[2].x=x[2].x;
v[2].y=x[2].y;
i=2;
j=3;
bur=2;
for(j=3;j<=n+1;++j)
{
bur++;
i=bur-1;
k=fgv(v[i-1].x,v[i-1].y,v[i].x,v[i].y,x[j].x,x[j].y);
if(k==1)
{
i++;
v[i].x=x[j].x;
v[i].y=x[j].y;
}
else if(k==0)
{
v[i].x=x[j].x;
v[i].y=x[j].y;
bur--;
}
else
{
while(fgv(v[i-1].x,v[i-1].y,v[i].x,v[i].y,x[j].x,x[j].y)==-1)
{
v[i].x=x[j].x;
v[i].y=x[j].y;
bur--;
i--;
}
while(fgv(v[i-1].x,v[i-1].y,v[i].x,v[i].y,x[j].x,x[j].y)==0)
{
v[i].x=x[j].x;
v[i].y=x[j].y;
bur--;
i--;
}
}
}
/*if(fgv(v[i-1].x,v[i-1].y,v[i].x,v[i].y,v[1].x,v[1].y)==0)
{
v[i-1].x=x[j].x;
v[i-1].y=x[j].y;
bur--;
}
{1}
bur++;
v[bur].x=ax;
v[bur].y=ay;
v[bur].h=h;
v[bur].n=0;*/
// cout<<bur-1<<"\n";
/*db=0;
for(i=1;i<bur;++i)
if(v[i+1].n!=1) db++;
{1}
cout<<db<<"\n";
{1}
for(i=1;i<bur;++i)
if(v[i+1].n!=1)
cout<<v[i].h<<" "<<v[i+1].h<<"\n";
*/
cout<<bur-1<<"\n";
for(i=1;i<bur;++i) cout<<setprecision(6)<<fixed<<v[i].x<<" "<<v[i].y<<"\n";
return 0;
}