Pagini recente » Cod sursa (job #1737064) | Cod sursa (job #2284047) | Cod sursa (job #873814) | Cod sursa (job #482826) | Cod sursa (job #2535751)
#include <fstream>
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
struct punct{
double x,y;
bool operator <(const punct& a) const
{
if(a.x==x)
return (a.y>y);
return (a.x>x);
}
};
vector<punct>v;
vector<punct>V;
vector<punct>b;
int determinant(punct a,punct b,punct c)
{
double u=(a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
if(u<=0)
return 0;
else
return 1;
}
void solve()
{
V.push_back(v[0]);
V.push_back(v[1]);
int k=2;
for(int i=2;i<n;i++)
{
while( k>1 &&determinant(V[k-2], V[k-1], v[i])==0 )
{
k--;
V.pop_back();
}
V.push_back(v[i]);
k++;
}
b.push_back(v[n-1]);
b.push_back(v[n-2]);
int aux=2;
for(int i=n-3;i>=0;i--)
{
while(aux >1 && determinant(b[aux-2], b[aux-1], v[i])==0)
{
aux--;
b.pop_back();
}
b.push_back(v[i]);
aux++;
}
V.pop_back();
b.pop_back();
int s=k+aux-2;
fout<<s<<"\n";
fout<<setprecision(6)<<fixed;
for(int i=0;i<k-1;i++)
{
fout<<V[i].x<<" "<<V[i].y;
fout<<"\n";
}
for(int i=0;i<aux-1;i++)
{
fout<<b[i].x<<" "<<b[i].y;
fout<<"\n";
}
}
int main( ) {
fin>>n;
v.resize(n);
for(int i=0;i<n;i++)
{
fin>>v[i].x>>v[i].y;
}
sort( v.begin(), v.end());
/*for(int i=0;i<n;i++)
{
fout<<v[i].x<< " " << v[i].y;
fout<<"\n";
}*/
solve();
return 0;
}