Pagini recente » Cod sursa (job #2522506) | Cod sursa (job #2421235) | Cod sursa (job #2909999) | Cod sursa (job #2744886) | Cod sursa (job #2936213)
#include <bits/stdc++.h>
#define nmax 120003
//#define float double
#define inf FLT_MAX
#define pi 3.14159
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct pt{
float x,y;
};
float pant(const pt &a, const pt &b)
{
return (b.x-a.x)/(b.y-a.y);
}
pt st;
pt s[nmax];
bool cmp(const pt &a, const pt &b)
{
return pant(st,a)>pant(st,b);
}
float cross(const pt &a, const pt &b, const pt &c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a,y)*(c.x-a.x);
}
int n;
pt stk[nkmax];
int k;
int main()
{
f>>n;
st.x=inf;
st.y=inf;
for(int i=0;i<n;i++)
{
f>>s[i].x>>s[i].y;
if(s[i].x<st.x) st=s[i];
else if(s[i].x==st.x&&s[i].y<st.y) st=s[i];
}
sort(s,s+n,cmp);
for(auto e:s)
{
stk[k++]=e;
while(k>3&&cross(stk[k-3],stk[k-2],stk[k-1])>0) k--;
}
for(int i=0;i<k;i++)
{
g<<fixed<<setprecision(6)<<stk[i].x<<','<<stk[i].y<<'\n';
}
return 0;
}