Cod sursa(job #2084060)

Utilizator patrickdanDan patrick patrickdan Data 8 decembrie 2017 16:39:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 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;
    for(j=2;j<=n;j++)
    {
        if(ccw(v[st[i-2]],v[st[i-1]],v[j])==1)
        {
            st.push_back(j);
            i++;
        }
        else
        {
            st.pop_back();
            j--;
            i--;
        }
    }
    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;
}