Cod sursa(job #2084053)

Utilizator patrickdanDan patrick patrickdan Data 8 decembrie 2017 16:20:21
Problema Infasuratoare convexa Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const double eps=1.e-12;
const double INF=2.e9;
vector<int>st;
int min1;
struct POINT
{
    double x,y;
};
POINT v[120005];
POINT temp1;
double cp(POINT p1,POINT p2,POINT p3)
{
    return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
}
int ccw(POINT p1,POINT p2,POINT p3)
{
    double c;
    c=cp(p1,p2,p3);
    if(fabs(c)<eps)
        return 0;
    if(c>=eps)
        return 1;
    return -1;
}
bool cmp(POINT a,POINT b)
{
    return ccw(temp1,a,b)>ccw(temp1,b,a);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n,i,j,a,b,ant;
    double x,y;
    scanf("%d",&n);
    v[0].x=v[0].y=1000000001;
    for(i=1;i<=n;i++)
    {
    scanf("%lf%lf",&x,&y);
    v[i].x=x;
    v[i].y=y;
    if(v[i].x-v[min1].x<=-eps)
        min1=i;
    else
        if(fabs(v[i].x-v[min1].x)<eps && v[i].y-v[min1].y<=-eps)
          min1=i;
    }
    temp1.x=v[min1].x;
    temp1.y=v[min1].y;
    for(i=min1;i<n;i++)
        v[i].x=v[i+1].x,v[i].y=v[i+1].y;
    v[n].x=temp1.x,v[n].y=temp1.y;
    n--;
    sort(v+1,v+n+1,cmp);
    st.push_back(n+1);
    st.push_back(1);
    ant=1;
    i=2;
    while(i<=n)
    {
        a=st[i-2];
        b=st[i-1];
        for(j=ant+1;j<=n;j++){
            if(ccw(v[a],v[b],v[j])==1)
            {
                st.push_back(j);
                ant=j;
                i++;
                break;
            }
            else
            {
              ant=st[i-1];
              st.pop_back();
              i--;
              break;
            }
        }
      if(ant==n)
        break;
    }
    printf("%d\n",st.size());
    for(i=1;i<st.size();i++)
        printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
    printf("%lf %lf\n",temp1.x,temp1.y);
    return 0;
}