Cod sursa(job #2067579)

Utilizator NastureNasture Anca Nasture Data 16 noiembrie 2017 17:04:14
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.41 kb
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<iostream>
#define MAX 1000000000
using namespace std;
struct punct{double x,y;
int parte;}v[120005];
int st[120005];
double arie(punct a, punct b, punct c){
    return a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
}
bool cmp(punct a, punct b){
    if(a.y<b.y)
        return true;
    else
        if(a.y>b.y)
            return false;
        else
            return (a.x<b.x);
}

int main(){
    double maxx=0, maxy=0, minx=MAX+MAX+100, miny=MAX+MAX+100;
    int poz,i,n,pozmin,pozmax;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%lf%lf",&v[i].x,&v[i].y);
        v[i].x+=MAX;
        v[i].y+=MAX;
        if(miny>v[i].y){
            pozmin=i;
            minx=v[i].x;
            miny=v[i].y;
        }
        else
            if(miny==v[i].y)
                if(v[i].x<minx){
                    pozmin=i;
                    minx=v[i].x;
                    miny=v[i].y;
                }
        if(maxy<v[i].y){
            pozmax=i;
            maxx=v[i].x;
            maxy=v[i].y;
        }
        else
            if(maxy==v[i].y)
                if(v[i].x<minx){
                    pozmax=i;
                    maxx=v[i].x;
                    maxy=v[i].y;
                }
    }
    for(i=1;i<=n;i++)
        if(i!=pozmin&&i!=pozmax)
            if(arie(v[pozmin],v[pozmax],v[i])<0)
                v[i].parte=1;
            else
                v[i].parte=-1;

sort(v+1,v+n+1,cmp);
int k;
st[1]=1;
i=2;
while(v[i].parte==-1)
    i++;
st[2]=i;
k=2;
int p;
double a;
p=v[st[2]].parte;
for(i=i+1;i<=n;i++)
        if(v[i].parte==p)
        {
            a=arie(v[st[k-1]],v[st[k]],v[i]);

            if(a*v[i].parte<0)
                st[k]=i;
            else
                st[++k]=i;
        }
st[++k]=n;
i=n-1;
p=-1;
while(v[i].parte==1)
    i--;
k++;
st[k]=i;
for(i=i-1;i>=2;i--)
    if(v[i].parte==p)
        {
            a=arie(v[st[k-1]],v[st[k]],v[i]);

            if(a*v[i].parte>0)
                st[k]=i;
            else
                st[++k]=i;
        }
printf("%d\n",k);

for(i=1;i<=k;i++)
    cout<<fixed<<setprecision(6)<<v[st[i]].x-MAX<<" "<<v[st[i]].y-MAX<<'\n';
    //printf("%.6lf %.6lf\n",v[st[i]].x-MAX,v[st[i]].y-MAX);
    return 0;
}