Pagini recente » Cod sursa (job #1887631) | Cod sursa (job #2778645) | Monitorul de evaluare | Cod sursa (job #851650) | Cod sursa (job #1279456)
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct punct{
double x, y;
};
const int nmax = 120006;
int n, lst, pozfirst;
punct v[nmax], first, st[nmax];
double det(punct a,punct b,punct c)
{
return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x);
}
bool compar(punct a, punct b)
{
return (det(a, first, b)>0);
}
int main(){
int player_unu=0;
first.x = 100000000000;
first.y = 100000000000;
in>>n;
for(int i = 0; i<n; i++)
{
in>>v[i].x>>v[i].y;
if(v[i].x==first.x && v[i].y<first.y)
{
first = v[i];
pozfirst = i;
}
if(v[i].x<first.x)
{
first = v[i];
pozfirst = i;
}
}
swap(v[pozfirst], v[0]);
sort(v + 1, v + n, compar);
st[0] = first;
lst = 1;
for(int i = 1; i<n; i++)
{
while(lst>1 && det(st[lst], st[lst - 1], v[i])>=0)
lst--;
st[lst] = v[i];
lst++;
}
out<<lst<<'\n';
out<<setprecision(6)<<fixed;
for(int i = 0; i<lst; i++)
out<<st[i].x<<' '<<st[i].y<<'\n';
return player_unu;
}