Pagini recente » Cod sursa (job #2960906) | Cod sursa (job #2277357) | Cod sursa (job #1851617) | Cod sursa (job #105525) | Cod sursa (job #1188381)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#define PI 3.1415926535897
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];
long 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 comp(infs a,infs b){
if(a.y==b.y)return a.x<b.x;
return a.y<b.y;
}
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)*180/PI>atan2(q[st[b]].y,q[st[b]].x)*180/PI;
}
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+1,q+n+1,comp);reverse(q+1,q+n+1);
sort(q+2,q+n+1,cmp);
solve();
//sort(st+2,st+nr+1,cmp2);
fout<<nr<<'\n';
for(int i=nr;i>=1;--i)fout<<fixed<<setprecision(12)<<q[st[i]].x<<' '<<q[st[i]].y<<'\n';
return 0;
}
void solve(){
st[++nr]=1;
st[++nr]=2;
for(int i=3;i<=n;++i){
while(nr>=2 and determin(q[st[nr]],q[st[nr-1]],q[i])<=0)--nr;
st[++nr]=i;
}
}