Pagini recente » Cod sursa (job #1313683) | Cod sursa (job #789358) | Cod sursa (job #2662759) | Cod sursa (job #54122) | Cod sursa (job #2552803)
#include <iostream>
#include <cstdio>
#include <vector>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int N = 120000;
struct punct{
double x, y;
} coord[N];
vector <punct> stiva1;
vector <punct> stiva2;
bool cmp(punct a, punct b){
if(a.y <= b.y)
return true;
return false;
}
double getArea(punct a, punct b, punct c){
double area = a.x * (b.y - c.y) - b.x * (a.y - c.y) + c.x * (a.y - b.y);
return area;
}
int main()
{
int n,i,top1,top2;
double area;
fin >> n;
for(i=0; i<n; i++)
fin >> coord[i].x >> coord[i].y;
sort(coord, coord+n, cmp);
stiva1.push_back(coord[0]);
stiva2.push_back(coord[0]);
for(i=1; i<n; i++){
area = getArea(coord[0], coord[n-1], coord[i]);
if(area <= 0){ /// dreapta
top2 = (int)stiva2.size();
while(top2 > 1 && getArea(stiva2[top2-2], stiva2[top2-1], coord[i]) <= 0){
stiva2.pop_back();
top2--;
}
stiva2.push_back(coord[i]);
}
if(area >= 0){ /// stanga
top1 = (int)stiva1.size();
while(top1 > 1 && getArea(stiva1[top1-2], stiva1[top1-1], coord[i]) >= 0){
stiva1.pop_back();
top1--;
}
stiva1.push_back(coord[i]);
}
}
top1 = (int)stiva1.size();
top2 = (int)stiva2.size();
fout << top1 + top2 - 2 << "\n";
fout << setprecision(6) << fixed;
for(i=0; i<top1; i++)
fout << stiva1[i].x << " " << stiva1[i].y << "\n";
for(i = top2 - 2; i > 0; i--)
fout << stiva2[i].x << " " << stiva2[i].y << "\n";
return 0;
}