Cod sursa(job #881816)

Utilizator dariusdariusMarian Darius dariusdarius Data 18 februarie 2013 17:40:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#define eps 1.e-12
#define inf 1.e9
using namespace std;
struct MyStruct {double x,y;} a;
vector<MyStruct> v;
inline double cp(const MyStruct &p1,const MyStruct &p2,const MyStruct &p3)
{
    return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
}
int st[120005];
class MyComp
{
public:
    inline bool operator()(const MyStruct &p,const MyStruct &q)
    {
        return cp(a,p,q)<-eps;
    }
};
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n,i,ind,top=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lf%lf",&a.x,&a.y),v.push_back(a);
    a=v[0];ind=0;
    for(i=1;i<(int)v.size();i++)
        if(v[i].x-a.x<-eps)
            ind=i,a=v[i];
        else
            if(fabs(v[i].x-a.x)<eps && v[i].y-a.y<-eps)
                ind=i,a=v[i];
    v.erase(v.begin()+ind);
    sort(v.begin(),v.end(),MyComp());
    v.push_back(a);
    st[++top]=v.size()-1;st[++top]=0;
    for(i=1;i<(int)v.size()-1;i++)
    {
        while(top>=2 && cp(v[st[top-1]],v[st[top]],v[i])>eps) {st[top]=0;top--;}
        st[++top]=i;
    }
    printf("%d\n",top);
    for(i=top;i>=1;i--)
        printf("%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
    return 0;
}