Pagini recente » Cod sursa (job #2701106) | Cod sursa (job #38855) | Cod sursa (job #356164) | Cod sursa (job #1893462) | Cod sursa (job #2199909)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <stack>
#define PI 3.14159265359
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct pct{ double x, y;};
stack < pct > s;
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 (a.x*b.y+b.x*c.y+a.y*c.x-b.y*c.x-b.x*a.y-a.x*c.y);
//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 afis()
{
if(!s.empty())
{
pct a = s.top();
s.pop();
afis();
g<<setprecision(6)<<fixed<<a.x<<" "<<a.y<<'\n';
}
}
void convex_hull(pct v[], int n)
{
s.push(lwst);
s.push(v[2]);
int idx=3;
pct a=lwst, b=v[2], c;
while(idx<=n)
{
long double d = det(a, b, v[idx]);
if(d>0)
{
s.push(v[idx]);
a=b;
b=v[idx];
}
else
{
b=a;
s.pop();
s.pop();
a=s.top();
d=det(a, b, v[idx]);
while(d<0)
{
b=a;
s.pop();
a=s.top();
d=det(a, b, v[idx]);
}
s.push(b);
s.push(v[idx]);
a=b;
b=v[idx];
}
idx++;
}
g<<s.size()<<'\n';
}
int main()
{
int n;
pct v[100001];
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);
afis();
}