Pagini recente » Cod sursa (job #2193385) | Cod sursa (job #1874363) | Cod sursa (job #834375) | Cod sursa (job #1668265) | Cod sursa (job #663092)
Cod sursa(job #663092)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef struct{
double x,y;
} str;
str v[120005];
int i,n,p,k,S[120005];
double xm,ym,X,Y;
bool cmp(str x,str y)
{
return (double)((y.y-Y)*(x.x-X))<(double)((y.x-X)*(x.y-Y));
}
bool coliniare(str x,str y,str z)
{
double sol=x.x*y.y+y.x*z.y+z.x*x.y-x.y*y.x-y.y*z.x-z.y*x.x;
return sol>0;
}
int main()
{
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
fi>>n;
xm=ym=int(2e9);
for(i=1;i<=n;i++)
{
fi>>v[i].x>>v[i].y;
if(v[i].x<xm) { xm=v[i].x; ym=v[i].y; p=i; } else
if(v[i].x==xm and v[i].y<ym) { ym=v[i].y; p=i; }
}
X=v[p].x; Y=v[p].y;
swap(v[p],v[n]);
sort(v+1,v+n,cmp);
for(i=1;i<=n;i++) if(X==v[i].x and Y==v[i].y) p=i;
S[++k]=p;
for(i=1;i<=n;i++)
{
if(i==p) continue;
while(k>=2 and coliniare(v[S[k-1]],v[S[k]],v[i])) k--;
S[++k]=i;
}
fo<<k<<"\n";
fo<<fixed;
fo<<setprecision(6);
for(i=k;i>0;i--) fo<<(double)(v[S[i]].x)<<" "<<(double)(v[S[i]].y)<<"\n";
return 0;
}