Pagini recente » Cod sursa (job #2029015) | Cod sursa (job #1663703) | Cod sursa (job #3141937) | Cod sursa (job #2963930) | Cod sursa (job #2199914)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define PI 3.14159265359
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct pct{ double x, y;};
pct sol[120001];
pct lwst;
void read(int &n, pct v[])
{
lwst.x=lwst.y=(1<<30);
f>>n;
for(int i=1; i<=n; i++)
{
f>>v[i].x>>v[i].y;
if(v[i].y<lwst.y)
lwst=v[i];
else if(v[i].y==lwst.y && v[i].x<lwst.x)
lwst=v[i];
}
}
double angle(pct a, pct b)
{
if(a.x==b.x && a.y==b.y)
return 0;
if(b.x==a.x)
return 90;
double rad = abs(atan(abs((b.y-a.y)/(b.x-a.x))));
double rez=abs(180*rad/PI);
if(a.x<b.x)
return 90-rez+90;
else return rez;
}
long double det(pct a, pct b, pct c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cond(const pct &a, const pct &b)
{
double ang1=angle(a, lwst);
double ang2=angle(b, lwst);
return (ang1<ang2);
}
void convex_hull(pct v[], int n)
{
int u=0;
sol[++u]=v[1];
sol[++u]=v[2];
for(int i=3; i<=n; i++)
{
while(u>1 && det(sol[u-1], sol[u], v[i])<0)
u--;
sol[++u]=v[i];
}
g<<u<<'\n';
for(int i=1; i<=u; i++)
g<<setprecision(6)<<fixed<<sol[i].x<<" "<<sol[i].y<<'\n';
}
int main()
{
int n;
pct v[120001];
read(n, v);
sort(v+1, v+n+1, cond);
/*for(int i=1; i<=n; i++)
cout<<v[i].x<<" "<<v[i].y<<" "<<angle(v[i], lwst)<<'\n';
cout<<lwst.x<<" "<<lwst.y<<'\n'<<'\n';
cout<<'\n'<<'\n';
for(int i=1; i<=n; i++)
cout<<v[i].x<<" "<<v[i].y<<'\n';
cout<<'\n';
cout<<v[5].x<<" "<<v[5].y<<" "<<v[7].x<<" "<<v[7].y<<" "<<v[8].x<<" "<<v[8].y<<endl;
cout<<det(v[5], v[7], v[8])<<"IVI";
cout<<'\n';*/
convex_hull(v, n);
}