Pagini recente » Cod sursa (job #1394395) | Cod sursa (job #1193812) | Cod sursa (job #2061990) | Cod sursa (job #135149) | Cod sursa (job #3168852)
#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],S[N];
double det(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)
{
return det(P[0],A,B)>=0;
}
int n,t;
int main()
{
f>>n;
int iMin=0;
for(int i=0;i<n;i++)
{
double x,y;
f>>x>>y;
P[i]=make_pair(x,y);
if(P[i]<P[iMin]) /// memorez pozitia unde perechea e cea mai mica
iMin=i;
}
swap(P[0],P[iMin]);
sort(P+1,P+n,crit);
S[++t]=P[0];S[++t]=P[1];
for(int i=2;i<n;i++)
{
while(det(S[t-1],S[t],P[i])<0)
t--;
S[++t]=P[i];
}
g<<t<<'\n';
for(int i=1;i<=t;i++)
g<<fixed<<setprecision(10)<<S[i].X<<' '<<S[i].Y<<'\n';
return 0;
}