Pagini recente » Cod sursa (job #2220139) | Cod sursa (job #1464770) | Cod sursa (job #20737) | Cod sursa (job #1524083) | Cod sursa (job #3030894)
#include <bits/stdc++.h>
#include <fstream>
#define cin fin
#define cout fout
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct puncte
{
double x,y;
};
puncte pct[120008];
bool compar(puncte a,puncte b)
{
return a.y<b.y || a.y==b.y && a.x<b.x;
}
int calculare(double x1,double y1,double x2,double y2,double x3,double y3)
{
double aux=x1*y2-x3*y2+x2*y3-y3*x1-x2*y1+y1*x3;
if(aux>=0)
return 1;
return -1;
}
int cnt,sol[120008],n,i;
double pct1,pct2;
int main()
{
cin>>n;
for(i=1;i<=n;i++)
{
cin>>pct[i].x>>pct[i].y;
}
sort(pct+1,pct+n+1,compar);
sol[0]=n;
sol[++cnt]=1;
for(i=2;i<=n;i++)
{
while(calculare(pct[sol[cnt-1]].x,pct[sol[cnt-1]].y,pct[sol[cnt]].x,pct[sol[cnt]].y,pct[i].x,pct[i].y)==1 && cnt>=1)
{
cnt--;
}
if(cnt!=0)
sol[++cnt]=i;
else
cnt++;
}
for(i=n-1;i>=1;i--)
{
while(calculare(pct[sol[cnt-1]].x,pct[sol[cnt-1]].y,pct[sol[cnt]].x,pct[sol[cnt]].y,pct[i].x,pct[i].y)==1 && cnt>=1)
{
cnt--;
}
if(cnt!=0)
sol[++cnt]=i;
else
cnt++;
}
cnt--;
cout<<cnt<<'\n';
for(i=cnt;i>=1;i--)
{
cout<<fixed<<setprecision(9)<<pct[sol[i]].x<<" "<<pct[sol[i]].y<<'\n';
}
return 0;
}