Pagini recente » Cod sursa (job #2649728) | Cod sursa (job #1113551) | Cod sursa (job #2143594) | Cod sursa (job #235284) | Cod sursa (job #2286236)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define MAX 120100
#define INT_MAX 2000000000
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{
double x;
double y;
}p[MAX], stiva[MAX], minim;
int pozm;
int n, vf;
bool m(punct x)
{
if(x.x < minim.x) return 1;
else if(x.x == minim.x)
if(x.y < minim.y) return 1;
return 0;
}
bool cmp(punct p1, punct p2){
int prod;
prod = p1.x * p2.y - p2.x * p1.y;
if(prod > 0) return 1;
else if(prod < 0) return 0;
else if(p1.x < p2.x) return 1;
else return 0;
}
bool cmp2(punct p1, punct p2, punct p3){
int prod;
p2.x -= p1.x; p2.y -= p1.y;
p3.x -= p1.x; p3.y -= p1.y;
prod = p2.x * p3.y - p3.x * p2.y;
if(prod > 0) return 1;
else if(prod < 0) return 0;
else if(p1.x < p2.x) return 1;
else return 0;
}
int main()
{int i;
minim.x = INT_MAX;
minim.y = INT_MAX;
fin >> n;
for(i = 1;i <= n; i++)
{
fin >> p[i].x;
fin >> p[i].y;
if(m(p[i]))
{
minim = p[i];
pozm = i;
}
}
swap(p[0], p[pozm]);
swap(p[pozm], p[n]);
for(i = 0;i < n; i++)
{
p[i].x -= minim.x;
p[i].y -= minim.y;
}
sort(p + 1, p + n, cmp);
stiva[1] = p[0];
stiva[2] = p[1];
vf = 2;
for(i = 2;i < n; i++)
{
if(cmp2(stiva[vf - 1], stiva[vf], p[i]))
{
vf++;
stiva[vf] = p[i];
}
else
{
vf--;
for(; vf >= 2; vf--)
{
if(cmp2(stiva[vf - 1], stiva[vf], p[i]))
{
vf++;
stiva[vf] = p[i];
break;
}
}
}
}
fout << vf << '\n';
//fout << fixed << setprecision(6) << stiva[1].x + minim.x << ' ' << stiva[1].y + minim.y <<'\n';
for(i=1;i<=vf;i++)
fout<< fixed << setprecision(6) << stiva[i].x + minim.x <<' '<<stiva[i].y + minim.y <<'\n';
return 0;
}