Pagini recente » Rezultatele filtrării | Cod sursa (job #3229550) | Cod sursa (job #1878369)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point{
double x,y;
};
point p[120001],st[120001];
int n,vf;
double det(point a, point b, point c){
return a.x*b.y+a.y*c.x+b.x*c.y-c.x*b.y-b.x*a.y-a.x*c.y;
}
bool cmp(point a,point b){
return det(p[1],a,b)<0;
}
int main(){
fin>>n;
for(int i=1;i<=n;i++)
fin>>p[i].x>>p[i].y;
fin.close();
int poz=1;
for(int i=2;i<=n;i++)
if(p[i].x<p[poz].x)
poz=i;
swap(p[1],p[poz]);
sort(p+2,p+n+1,cmp);
st[++vf]=p[1];
st[++vf]=p[2];
for(int i=3;i<=n;i++){
while(vf>=2&&det(st[vf-1],st[vf],p[i])>0)
vf--;
st[++vf]=p[i];
}
fout<<vf<<"\n";
for(int i=vf;i>0;i--)
fout<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";
fout.close();
return 0;
}