Pagini recente » Cod sursa (job #1007699) | Cod sursa (job #2578180) | Cod sursa (job #1788361) | Cod sursa (job #2941028) | Cod sursa (job #531308)
Cod sursa(job #531308)
#include<fstream>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
double x,y;
} p[120001],IN[120001];
int n,nr;
void read();
void solve();
void write();
int cmp(punct A,punct B);
double uhi(punct A,punct B,punct C);
double dist(punct A,punct B);
int main()
{
read();
solve();
write();
f.close();
g.close();
return 0;
}
void read()
{
int i;
f>>n;
for (i=1;i<=n;++i)
f>>p[i].x>>p[i].y;
}
void solve()
{
int i,pos;
double unghi;
pos=1;
for (i=2;i<=n;++i)
if ((p[i].y<p[pos].y)||(p[i].y==p[pos].y&&p[i].x<p[pos].x))
pos=i;
swap(p[1],p[pos]);
IN[1]=p[1];
sort(p+2,p+1+n,cmp);
IN[2]=p[2];
nr=2;
for (i=3;i<=n;++i)
{
unghi=uhi(IN[nr],p[i],IN[nr-1]);
while (unghi<0||(!unghi&&dist(IN[1],IN[i])>dist(IN[1],IN[nr])))
{
--nr;
unghi=uhi(IN[nr],p[i],IN[nr-1]);
}
IN[++nr]=p[i];
}
}
void write()
{
int i;
g<<nr<<'\n';
for (i=1;i<=nr;++i)
g<<IN[i].x<<' '<<IN[i].y<<'\n';
}
int cmp(punct A,punct B)
{
return (uhi(p[1],A,B)>0);
}
double uhi(punct A,punct B,punct C)
{
return (A.x*B.y+B.x*C.y+A.y*C.x-C.x*B.y-C.y*A.x-B.x*A.y);
}
double dist(punct A,punct B)
{
double t1,t2;
t1=A.x-B.x;
t2=A.y-B.y;
t1*=t1;
t2*=t2;
return sqrt(t1+t2);
}