Pagini recente » Cod sursa (job #2989419) | Cod sursa (job #1896960) | Cod sursa (job #331133) | simulare-oji-23-02-2024 | Cod sursa (job #2853698)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
int n;
struct punct{
double x,y;
}puncte[120001],punct_jos_stanga;
vector<punct>rasp;
int indice= -1;
int determinant(punct a,punct b,punct c)
{
return a.x*b.y + a.y*c.x + c.y*b.x - b.y*c.x - a.y*b.x - c.y*a.x;
}
bool cmp(punct a,punct b)
{
if(determinant(punct_jos_stanga,a,b)>0)
return true;
return false;
}
void gasire_punct()
{
punct_jos_stanga.x = 100000;
punct_jos_stanga.y = 100000;
for(int i = 1;i<=n;i++)
{
if(punct_jos_stanga.x>puncte[i].x)
{
punct_jos_stanga = puncte[i];
indice = i;
}
else
if(punct_jos_stanga.x==puncte[i].x && punct_jos_stanga.y>puncte[i].y)
{
punct_jos_stanga.y = puncte[i].y;
indice = i;
}
}
}
bool sens_cesornic(punct a,punct b,punct c)
{
if(determinant(a,b,c)<=0)
return true;
return false;
}
void alg()
{
rasp.push_back(punct_jos_stanga);
rasp.push_back(puncte[2]);
for(int i = 3;i<=n;i++)
{
while(sens_cesornic(rasp[rasp.size()-2],rasp[rasp.size()-1],puncte[i]))
rasp.pop_back();
rasp.push_back(puncte[i]);
}
}
void citire()
{
f >> n;
for(int i = 1;i<=n;i++)
{
f >> puncte[i].x>> puncte[i].y;
}
gasire_punct();
swap(puncte[1],puncte[indice]);
sort(puncte+2,puncte+1+n,cmp);
}
int main()
{
citire();
alg();
g << rasp.size()<< "\n";
for(int i = 0;i<rasp.size();i++)
{
g << fixed<< setprecision(6)<< rasp[i].x << " "<< setprecision(6)<< rasp[i].y<< "\n";
}
}