Pagini recente » Cod sursa (job #3269984) | Cod sursa (job #706765) | Cod sursa (job #680636) | Cod sursa (job #2363145) | Cod sursa (job #3213319)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct pct{
double x; double y;
}v[200001],st[200001];
pct ori;
int n;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
bool cmp(pct i, pct j) {
/*if(i.x==ori.x && i.y == ori.y)
return 0;
if(j.x==ori.x && j.y == ori.y)
return 1; */
return (i.x - ori.x) * (j.y - ori.y) > (j.x - ori.x) * (i.y - ori.y);
}
double semn(double xi1, double yi1,double xi2,double yi2, double xi3,double yi3) {
return xi1 * yi2 + xi2 * yi3 + xi3 * yi1 - yi1 * xi2 - yi2 * xi3 - yi3 * xi1;
}
int main(){
fin>>n;
ori.y = 1000000000;
for(int i=1;i<=n;i++){
fin>>v[i].x>>v[i].y;
if(v[i].y<ori.y)
ori=v[i];
else if(v[i].y==ori.y && v[i].x<ori.x)
ori=v[i];
}
for(int i=1;i<=n;i++)
v[i].x-=ori.x,v[i].y-=ori.y;
sort(v+1,v+n+1,cmp);
st[1]=v[1];
st[2]=v[2];
int k = 2;
for(int i = 3;i<=n;i++){
while(semn(st[k-1].x,st[k-1].y,st[k].x,st[k].y,v[i].x,v[i].y)<0){
k--;
}
st[++k]=v[i];
}
fout<<k<<'\n';
fout<<fixed<<setprecision(15);
fout<<st[k].x<<" "<<st[k].y<<'\n';
for(int i=1;i<k;i++)
fout<<st[i].x+ori.x<<" "<<st[i].y+ori.y<<'\n';
return 0;
}