Pagini recente » Atasamentele paginii Subsecvența de sumă maximă | Atasamentele paginii Profil 6jasminec352rL0 | Statistici Elsie Gibson (2jasminec4323th6) | Diferente pentru utilizator/andrei.arnautu intre reviziile 28 si 170 | Cod sursa (job #2191175)
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define l 123122
struct element
{
double x , y;
}v[l],sol[l];
bool fr[l];
int n , k;
bool Cross_Product(double ax , double ay , double bx , double by , double cx , double cy)
{
double x1 = ax-bx;
double x2 = ax-cx;
double y1 = ay-by;
double y2 = ay-cy;
return (y2*x1-y1*x2)>0;
}
void Solve()
{
int i , pos , poz;
double ax , ay , bx , by;
double mny = 0 , mxx = 99999999;
bool ok = 1 , flag;
fin >> n;
for ( i = 1 ; i <= n ; i ++ ){
fin >> v[i].x >> v[i].y;
if(mxx > v[i].x)
mxx = v[i].x , mny = v[i].y , pos = i;
}
fr[pos] = 1;
i = 1 , k = 1;
while(i == pos)
i++;
pos = i;
ax = mxx , ay = mny;
sol[k].x = ax , sol[k].y = ay;
bx = v[i].x , by = v[i].y;
while(ok)
{
flag = 1;
for ( i = 2 ; i <= n ; i ++ )
if(!fr[i] && i != pos)
{
if(Cross_Product(ax,ay,bx,by,v[i].x,v[i].y))
{
bx = v[i].x , by = v[i].y , poz = i , flag = 0;
}
}
if (!flag){
sol[++k].x = bx , sol[k].y = by , fr[poz] = 1 , pos = poz;
ax = sol[k].x , ay = sol[k].y , bx = sol[k-1].x , by = sol[k-1].y;}
else ok = 0;
}
fout << k <<'\n';
for ( i = k ; i >= 1 ; i -- )
fout << setprecision(12) << fixed << sol[i].x << " " << sol[i].y << '\n';
}
int main()
{
Solve();
}