Pagini recente » Cod sursa (job #730384) | Cod sursa (job #1793256) | Cod sursa (job #795269) | Cod sursa (job #2679242) | Cod sursa (job #1529083)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define MAX 120005
#define EPS le-12
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in"); ofstream g("infasuratoare.out");
typedef pair <double, double> Point;
Point V[MAX];
inline double Det(Point A, Point B, Point C)
{
return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}
inline bool cmp(Point A, Point B)
{
return (Det(V[1], A, B)<0);
}
int n, top, pos, S[MAX];
int main()
{
f>>n;
pos=1;
for(int i=1; i<=n; i++)
{
f>>V[i].x>>V[i].y;
if(V[i]<V[pos]) pos=i;
}
swap(V[1], V[pos]);
sort(V+2, V+n+1, cmp);
S[++top]=1;
for(int i=2; i<=n; i++)
{
while(top>1 and Det(V[S[top-1]], V[S[top]], V[i])>0) top--;
S[++top]=i;
}
g<<top<<'\n';
while(top)
{
g<<fixed<<setprecision(6)<<V[S[top]].x<<' '<<V[S[top]].y<<'\n';
top--;
}
g.close(); return 0;
}