Pagini recente » Cod sursa (job #2356113) | Cod sursa (job #1551016) | Cod sursa (job #1999230) | Cod sursa (job #424067) | Cod sursa (job #1596374)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{
double x, y;
};
punct v[120005], inf[120005];
int n, poz;
bool comp(punct a, punct b){
if(a.x < b.x)
return true;
if(a.x == b.y && a.y < b.y)
return true;
return false;
}
double sarrus(punct a, punct b, punct c){
return a.x * b.y + a.y * c.x + b.x * c.y - c.x * b.y - b.x * a.y - a.x * c.y;
}
int main()
{
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> v[i].x >> v[i].y;
sort(v + 1, v + 1 + n, comp);
for(int i = 1; i <= n; ++i){
while(poz >= 2 && sarrus(inf[poz - 1], inf[poz], v[i]) >= 0)
poz--;
poz++;
inf[poz] = v[i];
}
int nr1 = poz;
for(int i = n - 1; i >= 1; --i){
while(poz > nr1 && sarrus(inf[poz - 1], inf[poz], v[i]) >= 0)
poz--;
poz++;
inf[poz] = v[i];
}
fout << poz - 1 <<'\n';
fout << fixed;
for(int i = poz - 1; i >= 1; --i)
fout << setprecision(6) << inf[i].x << ' ' << inf[i].y << '\n';
return 0;
}