Pagini recente » Cod sursa (job #1317829) | Cod sursa (job #11958) | Cod sursa (job #398112) | Cod sursa (job #2164327) | Cod sursa (job #2202958)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <iostream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x, y;
};
punct stiva[120001],p[120001],sol[120001];
bool cmp (punct a, punct b) {
if (a.x < b.x)
return true;
else if (a.x > b.x)
return false;
else if (a.y < b.y)
return true;
else
return false;
}
double aria(punct a, punct b, punct c){
return (a.x-b.x)*(a.y+b.y)+(b.x-c.x)*(b.y+c.y)+(c.x-a.x)*(c.y+a.y);
}
int main()
{
int n, vf, cvf;
fin>>n;
for(int i=1; i<=n; i++){
fin>>p[i].x>>p[i].y;
}
sort(p+1, p+n+1, cmp);
vf=0;
stiva[++vf]=p[1];
for(int i=2; i<=n; i++){
while(vf>1 && aria(stiva[vf-1], stiva[vf], p[i])<0){
vf--;
}
stiva[++vf]=p[i];
}
for(int i=1; i<vf; i++)
sol[i] = stiva[i];
cvf=vf;
vf=0;
stiva[++vf]=p[n];
for(int i=n-1; i>=1; i--){
while(vf>1 && aria(stiva[vf-1], stiva[vf], p[i])<0){
vf--;
}
stiva[++vf]=p[i];
}
fout<<cvf+vf-2<<"\n";
for (int i = 2; i < cvf; i++)
fout<<fixed<<setprecision(6)<<sol[i].x<<" "<<sol[i].y<<"\n";
for (int i = 1; i < vf; i++)
fout<<fixed<<setprecision(6)<<stiva[i].x<<" "<<stiva[i].y<<"\n";
fout<<fixed<<setprecision(6)<<sol[1].x<<" "<<sol[1].y<<"\n";
return 0;
}