Pagini recente » Cod sursa (job #1391004) | Cod sursa (job #1540029) | Cod sursa (job #2835516) | Cod sursa (job #1049737) | Cod sursa (job #2403146)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
//-------------------------------
//Variabile globale
int n,rasp;
struct str
{
double x,y;
}v[120001],v2[120001];
//-------------------------------
//Functii
void citire();
void sortare();
bool comparare(str,str);
double comparare2(str,str,str);
void infasuratoare();
void afisare();
//-------------------------------
int main()
{
citire();
sortare();
infasuratoare();
afisare();
return 0;
}
//-------------------------------
void citire()
{
f >> n;
for(int i = 1;i <= n;++i)
f >> v[i].x >> v[i].y;
}
//-------------------------------
void sortare()
{
int pos = 1;
for(int i = 2; i <= n; ++i)
if(v[i].x < v[pos].x or (v[i].x == v[pos].x && v[i].y < v[pos].y))
pos = i;
swap(v[1], v[pos]);
sort(v + 2, v + n + 1, comparare);
}
//-------------------------------
bool comparare(str a,str b)
{
return comparare2(v[1],a,b) < 0;
}
//-------------------------------
double comparare2(str a,str b,str c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
//-------------------------------
void infasuratoare()
{
v2[1] = v[1];
v2[2] = v[2];
rasp = 2;
for(int i = 3;i <= n;++i)
{
while(rasp >= 2 && comparare2(v2[rasp - 1],v2[rasp],v[i]) > 0)
rasp--;
rasp++;
v2[rasp]=v[i];
}
}
//-------------------------------
void afisare()
{
g << rasp << '\n';
for(int i = rasp;i >= 1;--i)
g << fixed << setprecision(12) << v2[i].x << " " << v2[i].y << '\n';
}