Pagini recente » Cod sursa (job #376890) | Cod sursa (job #383079) | Cod sursa (job #1665983) | Cod sursa (job #2941889) | Cod sursa (job #1519975)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
#define punct pair<double, double>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
punct P[120010];
int n, i, t;
double X, Y;
bool crit_unghi(punct, punct);
double det(punct, punct, punct);
int main()
{
f>>n;
for(i=0;i<n;i++)
{
f>>X>>Y;
P[i] = make_pair(X, Y);
}
for(i=1;i<n;i++)
if(P[i]<P[0])
swap(P[i], P[0]);
sort(P+1, P+n, crit_unghi);
t=1;
for(i=2;i<n;i++)
{
while(det(P[t-1], P[t], P[i]) < 0)
t--;
P[++t]=P[i];
}
g<<t+1<<'\n';
for(i=0;i<=t;i++)
g<<fixed<<setprecision(6)<<P[i].x<<' '<<P[i].y<<'\n';
return 0;
}
bool crit_unghi(punct A, punct B)
{
return det(P[0], A, B) > 0.0;
}
double det(punct A, punct B, punct C)
{
return A.x*B.y+B.x*C.y+C.x*A.y-(A.y*B.x+B.y*C.x+C.y*A.x);
}