Pagini recente » Cod sursa (job #2210647) | Cod sursa (job #2713321) | Cod sursa (job #2465426) | Cod sursa (job #2566105) | Cod sursa (job #2535654)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
int n,m,q;
struct punct{
double x,y;
bool operator <(punct p)
{
if(p.x==x)
return(y<p.y);
return(x<p.x);
}
};
vector<punct>v;
punct a[120003],b[120003];
void citire()
{
ifstream fin("infasuratoare.in");
fin>>n;
for(int i=0;i<n;i++)
{
double a,b;
punct p;
fin>>a>>b;
p.x=a;
p.y=b;
v.push_back(p);
}
sort(v.begin(),v.end());
}
int sens(punct a,punct b,punct c)
{
double det;
det=(a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
if(det<=0)
return 0;
return 1;
}
void rezolvare()
{
a[0]=v[0];
a[1]=v[1];
m=2;
for(int i=2;i<n;i++)
{
while(m>1&&!sens(a[m-2],a[m-1],v[i]))
m--;
a[m++]=v[i];
}
b[0]=v[n-1];
b[1]=v[n-2];
q=2;
for(int i=n-3;i>=0;i--)
{
while(q>1&&!sens(b[q-2],b[q-1],v[i]))
q--;
b[q++]=v[i];
}
}
void afisare()
{
ofstream fout("infasuratoare.out");
fout<<m+q-2<<"\n";
fout<<setprecision(6)<<fixed;
for(int i=0;i<m-1;i++)
fout<<a[i].x<<" "<<a[i].y<<"\n";
for(int i=0;i<q-1;i++)
fout<<b[i].x<<" "<<b[i].y<<"\n";
}
int main()
{
citire();
for(int i=0;i<n;i++)
cout<<v[i].x<<" "<<v[i].y<<"\n";
rezolvare();
afisare();
return 0;
}