Pagini recente » Cod sursa (job #825031) | Cod sursa (job #2969200) | Cod sursa (job #574352) | Cod sursa (job #1953968) | Cod sursa (job #1188359)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
const int MAX = 1<<17;
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct infs{
long double x,y;
};
infs q[MAX];
double determin(infs a,infs b,infs c){
return 1LL*(b.x-a.x)*(c.y-a.y)-1LL*(b.y-a.y)*(c.x-a.x);
}
bool cmp(infs a,infs b){
return determin(q[1],a,b)<0;
}
int st[MAX],itmin,n,nr;
bool cmp2(int a,int b)
{
return atan2(q[st[a]].y,q[st[a]].x)<atan2(q[st[b]].y,q[st[b]].x);
}
void solve();
int main()
{
long double ymin=1<<29,xmin=1<<29;
fin>>n;
for(int i=1;i<=n;++i){
fin>>q[i].x>>q[i].y;
if(ymin>q[i].y){
ymin=q[i].y;
itmin=i;
}
else if(ymin==q[i].y){
if(xmin>q[i].x)xmin=q[i].x,itmin=i;
}
}
swap(q[itmin],q[1]);
sort(q+2,q+n+1,cmp);
solve();
sort(st+1,st+nr+1,cmp2);
fout<<nr<<'\n';
for(int i=1;i<=nr;++i)fout<<fixed<<setprecision(12)<<q[st[i]].x<<' '<<q[st[i]].y<<'\n';
return 0;
}
void solve(){
st[++nr]=1;
st[++nr]=2;
st[++nr]=3;
for(int i=4;i<=n;++i){
while(nr>0 and determin(q[st[nr]],q[st[nr-1]],q[i])<0)--nr;
st[++nr]=i;
}
}