Pagini recente » Cod sursa (job #2661938) | Cod sursa (job #1755457) | Cod sursa (job #1353213) | Cod sursa (job #2954897) | Cod sursa (job #2748526)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int hull[120005];
struct Point{
double x,y;
}P1,P2,P3,v[120005];
double cross_product(Point a,Point b,Point c){
return (a.x-b.x)*(a.y-c.y)-(a.y-b.y)*(a.x-c.x);
}
bool ms(Point a,Point b){
return (cross_product(v[1],a,b)>=0);
}
int main()
{
int n,mini=1;
fin>>n;
for(int i=1;i<=n;i++){
fin>>v[i].x>>v[i].y;
if(v[mini].y>v[i].y){
mini=i;
}
}
swap(v[1],v[mini]);
sort(v+2,v+n+1,ms);
v[++n]=v[1];
hull[1]=1;
int cnt=1;
for(int i=1;i<=n;i++){
while(cnt>1 and cross_product(v[hull[cnt-1]],v[hull[cnt]],v[i])<=0){
cnt--;
}
hull[++cnt]=i;
}
cnt--;
fout<<cnt<<"\n";
for(int i=1;i<=cnt;i++){
fout<<fixed<<setprecision(6);
fout<<v[hull[i]].x<<" "<<v[hull[i]].y<<"\n";
}
return 0;
}