Pagini recente » Cod sursa (job #1510878) | Cod sursa (job #2165537) | Cod sursa (job #636079) | Cod sursa (job #1017269) | Cod sursa (job #2414785)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const double kEps=1e-9;
struct pct{
double x=0,y=0;
} a[120010],b[120010];
int n,i,k;
double DET(pct a,pct b,pct c){
// a.x a.y 1
// b.x b.y 1
// c.x c.y 1
return (a.x*b.y+a.y*c.x+b.x*c.y)-(c.x*b.y+a.x*c.y+b.x*a.y);
}
int sgn(double val){
if(abs(val)<kEps)return 0;
if(val>kEps)return 1;
return -1;
}
inline double dst(pct A,pct B){
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
bool comp(pct A,pct B){
double Asin=(A.y-a[1].y)/dst(A,a[1]);
double Bsin=(B.y-a[1].y)/dst(B,a[1]);
if(abs(Asin-Bsin)<kEps)
return dst(A,a[1])<dst(B,a[1]);
else
return Asin<Bsin;
}
int main()
{
f>>n;
for(i=1;i<=n;i++){
f>>a[i].x>>a[i].y;
if(a[i].x<a[1].x||(a[i].x==a[1].x&&a[i].y<a[1].y))
swap(a[i],a[1]);
}
sort(a+2,a+n+1,comp);
b[1]=a[1];
b[2]=a[2];k=2;
// int matr[110][110];
// memset(matr,0,sizeof(matr));
// for(i=1;i<=n;i++)
// {
// g<<a[i].x<<' '<<a[i].y<<'\n';
// matr[(int)a[i].y][(int)a[i].x]=i;
// }
// for(i=10;i>=0;i--){
// for(int j=0;j<=10;j++)
// g<<matr[i][j]<<' ';
// g<<'\n';
// }
for(i=3;i<=n;i++){
while(k>=2&&sgn(DET(b[k-1],b[k],a[i]))!=1)
k--;
b[++k]=a[i];
}
g<<k<<'\n';
for(i=2;i<=k;i++)
g<<fixed<<setprecision(10)<<b[i].x<<' '<<b[i].y<<'\n';
g<<fixed<<setprecision(10)<<b[1].x<<' '<<b[1].y<<'\n';
return 0;
}