Pagini recente » Cod sursa (job #2453757) | Cod sursa (job #1628217) | Cod sursa (job #1154) | Cod sursa (job #1683875) | Cod sursa (job #1882756)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
#define NMAX 120001
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
struct punct
{
double x, y;
friend istream& operator>>(istream &in,punct &p)
{
in>>p.x>>p.y;
return in;
}
friend ostream& operator<<(ostream &out,punct &p)
{
out<<setprecision(6)<<p.x<<' '<<setprecision(6)<<p.y<<'\n';
return out;
}
}puncte[NMAX];
vector<punct> stiva;
punct most_left;
int most_left_index;
double det(punct a, punct b,punct c)
{
return (a.x-b.x)*(b.y-c.y) - (a.y-b.y)*(b.x-c.x);
}
bool comparator(punct a,punct b)
{
return det(a,b,most_left) < 0;
};
void citire()
{
f>>n>>puncte[0];
most_left=puncte[0];
for(int i=1;i<n;i++)
{
f>>puncte[i];
if(puncte[i].x<most_left.x)
{
most_left = puncte[i];
most_left_index = i;
}
}
swap(puncte[most_left_index],puncte[0]);
sort(puncte+1,puncte+n,comparator);
stiva.push_back(puncte[0]);
stiva.push_back(puncte[1]);
// puncte[n] = puncte[0];
}
punct first()
{
return stiva[stiva.size()-1];
}
punct second()
{
return stiva[stiva.size()-2];
}
void infasuratoare()
{
for (int i = 2; i < n; i++)
{
while (stiva.size() >= 2 && det(second(), first(), puncte[i]) > 0)
stiva.pop_back();
stiva.push_back(puncte[i]);
}
g<<stiva.size()<<'\n';
g<<setiosflags(ios::fixed);
for (int i = stiva.size()-1; i >= 0; i--)
g<<stiva[i];
}
int main()
{
citire();
infasuratoare();
return 0;
}