Pagini recente » Cod sursa (job #2331636) | Cod sursa (job #1993772) | Cod sursa (job #1597779) | Cod sursa (job #2751769) | Cod sursa (job #1242236)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define PDD pair < double , double >
#define NMAX 120500
#define F first
#define S second
PDD P[NMAX];
int _i,i,N;
vector < int > Q;
double w(PDD A,PDD B,PDD C)
{
return (A.F-C.F)*(B.S-C.S)-(B.F-C.F)*(A.S-C.S);
}
bool compare(PDD A,PDD B)
{
return (w(P[1],A,B)>0);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
for (i=_i=1,scanf("%d",&N);i<=N;++i)
{
scanf("%lf%lf",&P[i].F,&P[i].S);
if (_i>=2 && P[i]<P[_i]) _i=i;
}
swap(P[1],P[_i]);
sort(P+2,P+N+1,compare);
Q.push_back(1);
Q.push_back(2);
for (i=3;i<=N;++i)
{
while (Q.size()>=2 && w(P[Q[Q.size()-1]],P[Q[Q.size()-2]],P[i])>=0) Q.pop_back();
Q.push_back(i);
}
printf("%d\n",Q.size());
for (i=0;i<Q.size();++i)
printf("%.7lf %.7lf\n",P[Q[i]].F,P[Q[i]].S);
return 0;
}