Pagini recente » Cod sursa (job #2221932) | nyes | Cod sursa (job #2570808) | Cod sursa (job #1927570) | Cod sursa (job #1202917)
#include<fstream>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<algorithm>
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
const double pi = 3.141592653589;
const int maxn = 120005;
struct punct{
double x;
double y;
double p;
};
double min_x,min_y;
punct a[maxn];
int i,n,poz;
int t[maxn];
int semn_det(punct a,punct b,punct c){
if(a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x>0) return 1;
else return (-1);
}
double polar(double x,double y){
if(x>0){
if(y>0) return atan(y/x);
else return atan(y/x)+2*pi;
}
else if(x<0) return atan(y/x)+pi;
else if(x==0){
if(y>0) return pi/2;
else if(y<0) return 3*pi/2;
else return 0.0;
}
}
bool comp(punct a,punct b){
return (a.p<b.p);
}
int main(){
fi>>n;
for(i=1;i<=n;i++) fi>>a[i].x>>a[i].y;
min_x=a[1].x; min_y=a[1].y;
for(i=2;i<=n;i++)
if(a[i].y<min_y){
min_x=a[i].x;
min_y=a[i].y;
}
for(i=1;i<=n;i++) a[i].p=polar(a[i].x-min_x,a[i].y-min_y);
sort(a+1,a+n+1,comp);
t[1]=1; t[2]=2; poz=2;
for(i=3;i<=n;i++)
if(semn_det(a[t[poz-1]],a[t[poz]],a[i])>0) t[++poz]=i;
else{
while(semn_det(a[t[poz-1]],a[t[poz]],a[i])<0) poz--;
t[++poz]=i;
}
fo<<poz<<"\n";
for(i=1;i<=poz;i++)
fo<<fixed<<setprecision(7)<<a[t[i]].x<<" "<<fixed<<setprecision(7)<<a[t[i]].y<<"\n";
fi.close();
fo.close();
return 0;
}