Pagini recente » Cod sursa (job #1256513) | Cod sursa (job #647365) | Cod sursa (job #2116267) | Cod sursa (job #1704293) | Cod sursa (job #2925808)
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int N = 120010;
typedef pair<double,double> punct;
punct P[N],st[N];
int n,k;
double delta(punct A,punct B,punct C)
{
double ret=(A.X*B.Y+B.X*C.Y+C.X*A.Y)-(A.Y*B.X+B.Y*C.X+C.Y*A.X);
return ret;
}
bool crit(punct A,punct B)
{
double d=delta(P[0],A,B);
/// daca P[0],A, vede B in stanga atunci A si B sunt asezate corect in sortare
if(d>0)return true;
return false;
}
int main()
{
/// citire
f>>n;
for(int i=0;i<n;i++)
{
double x,y;
f>>x>>y;
P[i]=make_pair(x,y);
}
/// alegem punctul situat cel mai la dreapta si daca am mai multe - cel mai jos
int i=0;
for(int j=1;j<n;j++)
if(P[j]<P[i])
i=j;
/// il mutam la inceput
swap(P[0],P[i]);
/// sortam punctele trigononetric fata de P[0]
sort(P+1,P+n,crit);
/// punem in stiva P[0] si P[1]
st[0]=P[0];st[1]=P[1];
k=1;
for(int j=2;j<n;j++)
{
/// pentru fiecare punct:
/// eliminam ultimul punct din stiva cat timp punctul nou se vede in dreapta
while(k>1&&delta(st[k-1],st[k],P[j])<=0)
k--;
/// apoi adaugam punctul nou
k++;
st[k]=P[j];
}
/// afisare:
g<<k+1<<'\n';
for(int i=0;i<=k;i++)
g<<fixed<<setprecision(10)<<st[i].X<<' '<<st[i].Y<<'\n';
return 0;
}