Pagini recente » Cod sursa (job #1684886) | Cod sursa (job #1432668) | Cod sursa (job #510037) | Cod sursa (job #2941672) | Cod sursa (job #2723337)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstdlib>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const double INF = 2000000000.0;
const int NMAX = 120005;
struct point
{
double x,y;
point(){}
point(int x,int y)
{
this->x = x;
this->y = y;
}
bool operator==(const point &other) const{
return ((x == other.x) && (y == other.y));
}
bool operator<(const point &other) const{
return ((y*other.x) < (x*other.y));
}
};
int semn(point a,point b,point c)
{
double val = (a.x-b.x)*(a.y-c.y)-(a.y-b.y)*(a.x-c.x);
if(val >= 0) return 1;
return -1;
}
int n;
vector<point>p;
point st[NMAX];
int top = 0;
point LL;
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);fout.tie(0);
LL.x = INF;
LL.y = INF;
fin >> n;
for(int i = 1 ; i <= n ; i++)
{
point temp;
fin >> temp.x >> temp.y;
p.push_back(temp);
if(LL.y > temp.y)
{
LL.x = temp.x;
LL.y = temp.y;
}
else if(LL.y == temp.y && LL.x > temp.x)
LL.x = temp.x;
}
for(int i = 1 ; i < p.size() ; i++)
{
if(p[i] == LL)
swap(p[0],p[i]);
p[i].x -= LL.x;
p[i].y -= LL.y;
}
p[0] = point({0,0});
sort(p.begin()+1,p.end());
st[++top] = p[0];
st[++top] = p[1];
st[++top] = p[2];
for(int i = 3 ; i < p.size() ; i++)
{
while(top >= 2 && semn(st[top-2],st[top-1],st[top]) != semn(st[top-1],st[top],p[i]))
top--;
st[++top] = p[i];
}
fout << top << '\n';
for(int i = 1 ; i <= top ; i++)
fout << fixed << setprecision(6) << st[i].x + LL.x << ' ' << st[i].y + LL.y << '\n';
return 0;
}