Cod sursa(job #1344545)

Utilizator koroalinAlin Corodescu koroalin Data 16 februarie 2015 20:06:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.44 kb
#include <cstdio>
#include <cmath>
#include <list>
#include <algorithm>
#define NMAX 120002
#define INF 1<<29
using namespace std;
FILE* fin=fopen("infasuratoare.in","r");
FILE* fout=fopen("infasuratoare.out","w");
int n;
struct punct
{
    double x,y;
    double r;
    double t;
};
punct pct[NMAX];
list <punct> P;
bool comp(punct a,punct b);
double produs (punct a,punct b,punct c);
void citire();
void afisare();
int main()
{
    int i;
    citire();
    sort(pct+1,pct+n+1,comp);
    P.push_back(pct[n]);
    for (i=1; i<=n; i++)
        P.push_back(pct[i]);
    P.push_back(pct[1]);
    list<punct>::iterator it;
    list<punct>::iterator it1,it2,it3;
    it1=it2=it3=P.begin();
    it2++; it3++; it3++;
    while (it3 != P.end())
    {
        //afisare();
        if (produs (*it1,*it2,*it3)>0)
        {
            it1++;
            it2++;
            it3++;
            continue;
        }
        P.erase(it2);
        it2=it1;
        it1--;
    }
    //afisare();
    fprintf(fout,"%d\n",P.size()-2);
    it=P.begin();
    it1=P.end(); it1--;
    it++;
    while (it!=it1)
    {
        fprintf(fout,"%lf %lf\n",it->x,it->y);
        it++;
    }
    return 0;
}
void citire()
{
    int i;
    double xmin,ymin;
    fscanf(fin,"%d",&n);
    xmin=ymin=INF;
    for (i=1; i<=n; i++)
    {
        fscanf(fin,"%lf %lf",&pct[i].x,&pct[i].y);
        if (pct[i].x<xmin)
        {
            xmin=pct[i].x; ymin=pct[i].y;
        }
        else
        {
            if (pct[i].x==xmin)
            {
                if (pct[i].y<ymin)
                {
                    xmin=pct[i].x; ymin=pct[i].y;
                }
            }
        }
    }
    for (i=1; i<=n; i++)
    {
        pct[i].r=sqrt((pct[i].x-xmin)*(pct[i].x-xmin) + (pct[i].y - ymin)*(pct[i].y -ymin));
        if (pct[i].x != xmin)
            pct[i].t=(pct[i].y -ymin)/(pct[i].x-xmin);
        else
        {
            if (pct[i].y == ymin) pct[i].t=-INF;
            else pct[i].t=INF;
        }
    }
}
bool comp(punct a,punct b)
{
    if (a.t<b.t) return 1;
    if (a.t==b.t) if (a.r<b.r) return 1;
    return 0;
}
double produs(punct a,punct b,punct c)
{
    return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
void afisare()
{
    list<punct>::iterator it;
    for (it=P.begin(); it!=P.end(); it++)
    {
        fprintf(fout,"%.0lf %.0lf   ",it->x,it->y);
    }
    fprintf(fout,"\n");
}