Cod sursa(job #1883182)

Utilizator alex.craciunCraciun Alexandru alex.craciun Data 17 februarie 2017 19:46:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <limits.h>
using namespace std;
int n;
struct punct
{
    double x,y;
} v[120020],coada[120020];
int mini=INT_MAX;
void citire( )
{
    FILE *f=fopen("infasuratoare.in","r");
    fscanf(f,"%d",&n);
    int poz;
    for(int i=1; i<=n; i++)
    {
        fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
        if(v[i].x<mini)
        {
            mini=v[i].x;
            poz=i;
        }
        else if(v[i].x==mini)
            if(v[i].y<v[poz].y)
            {
                poz=i;
            }


    }
    swap(v[1],v[poz]);

}
double sbp(punct p1,punct p2, punct p3)
{
    double prod= (p2.x - p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y);

    return prod;
}
bool comp(punct p1, punct p2)
{
    return (sbp(v[1],p1,p2))>0;
}
void rez( )
{
    sort(v+2,v+n+1,comp);
    int k=0;
    coada[++k]=v[1];
    coada[++k]=v[2];
    for(int i=3; i<=n; i++)
    {
        while(k>=2&&sbp(coada[k-1],coada[k],v[i])<0)
            k--;
        coada[++k]=v[i];

    }
    FILE *f1=fopen("infasuratoare.out","w");
    fprintf(f1,"%d\n",k);
    for(int i=1; i<=k; i++)
        fprintf(f1,"%lf %lf\n",coada[i].x,coada[i].y);

}
int main()
{
    citire();
    rez();
    return 0;
}