Cod sursa(job #1395422)

Utilizator dany3608Tyekar Dan dany3608 Data 21 martie 2015 11:38:22
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.27 kb
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
int n;
double sum=0;
struct str
{
       double x;
       double y;
       double n1;
       double n2;
}a[120001],b[120001],q;
double comp(str a,str b)
{
    return (a.n1*b.n2) < (b.n1*a.n2);
}
double calcarie(double x1,double y1,double x2,double y2,double x3,double y3)
{
       double arie=double((double)x1*(y2-y3)+(double)x2*(y3-y1)+(double)x3*(y1-y2));
       arie=(double)arie/2;
       return arie;
}
int stack[120001];
int pint,nr,m;
int main()
{

    ifstream f("geometrie.in");
    ofstream g("geometrie.out");
    f>>nr>>m;
    for (int i=1;i<=nr ;i++ )
    	f>>b[i].x>>b[i].y;
for (int qiu=1;qiu<=m ;qiu++ )
{
    f>>q.x>>q.y;
    int n=0;
    for (int i=1;i<=nr ;i++ )
    	if(b[i].x<q.x)
            {
                n++;
                a[n]=b[i];
            }
    n++; a[n]=q;
    double minx=1000000001,miny=1000000001;
    int indice;
    for(int i=1;i<=n;i++)
    {
            if(minx>a[i].x)
            {
                           minx=a[i].x;
                           miny=a[i].y;
                           indice=i;
            }
            else if(minx==a[i].x&&miny>a[i].y)
            {
                 miny=a[i].y;
                 indice=i;
            }
    }
    for(int i=1;i<indice;i++)
    {
            a[i].n1=a[i].y-a[indice].y;
            a[i].n2=a[i].x-a[indice].x;
    }
    for(int i=indice+1;i<=n;i++)
    {
            a[i].n1=a[i].y-a[indice].y;
            a[i].n2=a[i].x-a[indice].x;
    }
    swap(a[1],a[indice]);
    sort(a+2,a+n+1,comp);
    stack[1]=1;
    stack[2]=2;
    pint=3;
    for(int i=3;i<=n;i++)
    {
            while(calcarie(a[stack[pint-2]].x,a[stack[pint-2]].y,a[stack[pint-1]].x,a[stack[pint-1]].y,a[i].x,a[i].y)<0) pint--;
            stack[pint]=i;
            pint++;
    }
    //pint-1=n;
    a[stack[0]]=a[stack[pint-1]];
    int i,j,k;
    sum=0;
    for ( i=1, j=2, k=0; i<pint-1; i++, j++, k++)      //a[stack[i]].x   //a[stack[i]].y
    	sum=sum+a[stack[i]].x*(a[stack[j]].y-a[stack[k]].y);  // V[n].x * (V[1].y - V[n-1].y);
    	sum=sum+a[stack[pint-1]].x*(a[stack[1]].y-a[stack[pint-2]].y);

    	g<<fixed<<setprecision(1)<<sum/2<<'\n';

    }
}