Pagini recente » Cod sursa (job #1255530) | Cod sursa (job #2108583) | Cod sursa (job #2987987) | Cod sursa (job #1033352) | Cod sursa (job #1115717)
#include <fstream>
#include <stack>
#include <iomanip>
#include <algorithm>
using namespace std;
#define Point pair<double, double>
#define x first
#define y second
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const double eps = 0.0000000000001;
const int NMAX = 120009;
Point V[NMAX]; int N; Point S[NMAX];
double sarrus(const Point& A, const Point& B, const Point& C){
double a = A.y - B.y;
double b = B.x - A.x;
double c = A.x * B.y - A.y * B.x;
return a * C.x + b * C.y + c;
}
bool cmp(const Point& A, const Point& B) {
return sarrus(V[1], A, B) < 0 ;
}
int main() {
fin >> N; int ind = 1;
for(int i = 1; i <= N; ++i) {
fin >> V[i].x >> V[i].y;
if(V[i] < V[ind]) ind = i;
}
swap(V[ind], V[1]);
sort(V + 2, V + 1 + N, cmp);
S[1] = V[1]; S[2] = V[2];
int sz = 2;
for(int i = 3; i <= N; ++i) {
while(sz >= 2 && sarrus(S[sz - 1], S[sz], V[i]) > 0) sz--;
S[++sz] = V[i];
}
fout << fixed ;
fout << sz <<'\n';
for(int i = sz; i ; --i)
fout << setprecision(6) << S[i].x << " " << S[i].y <<'\n';
return 0;
}