Cod sursa(job #2402104)

Utilizator MarutBrabete Marius Stelian Marut Data 10 aprilie 2019 12:40:46
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
struct POINT
{
    double x,y;
};
const double eps=1e-8;
POINT LL;
vector<POINT>v;
double cp(POINT P1, POINT P2, POINT P3)
{
    return (P3.y-P2.y)*(P2.x-P1.x) - (P3.x-P2.x)*(P2.y-P1.y);
}
int ccw(POINT P1, POINT P2, POINT P3)
{
    double cpp=cp(P1,P2,P3);
    if(fabs(cpp)<eps) return 0;
    if(cpp>eps) return 1;
    return -1;
}
bool cmp(POINT P1, POINT P2)
{
    int cccw=ccw(LL,P1,P2);
    return cccw==1;
}
int h[120005];
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n;
    scanf("%d",&n);
    double x,y,xL,yL;
    POINT temp;
    scanf("%lf%lf",&xL,&yL);
    temp.x=xL;
    temp.y=yL;
    v.push_back(temp);
    for(register int i=2;i<=n;i++)
    {
        scanf("%lf%lf",&x,&y);
        temp.x=x;
        temp.y=y;
        v.push_back(temp);
        if((fabs(v[0].y-y)<eps&&(x-v[0].x)<(-eps))||(y-v[0].y<(-eps)))  swap(v[0],v[i-1]);
    }
    LL.x=v[0].x;
    LL.y=v[0].y;
    sort(v.begin()+1,v.end(),cmp);
  //  for(register int i=0;i<=v.size();i++)
     //   printf("%lf %lf\n",v[i].x,v[i].y);
    h[1]=0;
    h[2]=1;
    int top=2,i=2;
    while(i<n)
    {
        if(ccw(v[h[top-1]],v[h[top]],v[i])>0)
        {
            h[++top]=i;
            i++;
        }
            else top--;
    }
 //   for(i=1;i<=top;i++)
    //    printf("%d \n",h[i]);
    printf("%d\n",top);
    for(i=1;i<=top;i++)
        printf("%d ",h[i]);
    printf("\n");
    for(i=1;i<=top;i++)
        printf("%lf %lf\n",v[h[i]].x,v[h[i]].y);
    return 0;
}