Pagini recente » Cod sursa (job #1385699) | Cod sursa (job #1230615) | Cod sursa (job #2963290) | Cod sursa (job #1945342) | Cod sursa (job #1361722)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <stack>
#define point pair<double,double>
#define nmax 120002
#define eps 0.000001
using namespace std;
ifstream is ("infasuratoare.in");
ofstream os ("infasuratoare.out");
point V[nmax];
int S[nmax];
struct Comp{
bool operator()(const point& B, const point& C) {
return (B.first - V[1].first) * (C.second - V[1].second) -
(B.second - V[1].second) * (C.first - V[1].first) > 0;
}
};
int N, poz1;
void Read();
bool Cmp(int,int,int);
int main()
{
Read();
V[0].second = 1000000000;
for(int i = 1; i <= N; ++i)
{
if(V[i].first == V[poz1].first)
if(V[i].first < V[poz1].first)
poz1 = i;
if(V[i].second < V[poz1].second)
poz1 = i;
}
swap(V[1], V[poz1]);
sort(V+2, V+N+1, Comp());
S[1] = 1;
S[2] = 2;
int top = 2;
for(int i = 3; i <= N; ++i)
{
while(top >= 2 && Cmp(S[top-1], S[top], i))
top--;
S[++top] = i;
}
os << top << "\n";
for(int i = 1; i <= top; ++i)
os << fixed << setprecision(6) << V[S[i]].first << " " << V[S[i]].second << "\n";
is.close();
os.close();
return 0;
}
void Read()
{
double x, y;
is >> N;
for(int i = 1; i <= N; ++i)
is >> V[i].first >> V[i].second;
}
bool Cmp(int a,int b,int c)
{
point A = V[a];
point B = V[b];
point C = V[c];
return (B.first - A.first) * (C.second - A.second) -
(B.second - A.second) * (C.first - A.first) < 0;
}