Cod sursa(job #2322611)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 17 ianuarie 2019 22:40:22
Problema Infasuratoare convexa Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.14 kb
#include <bits/stdc++.h>
#define det(A,B,C) (A.first*B.second+B.first*C.second+C.first*A.second)-(C.first*B.second+B.first*A.second+A.first*C.second)
#define dist(A,B) (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second)

const double mic=1e-7;

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n,i,j,iq,k,nxt[120010];
pair<double,double> P[120010],V[120010];

double Dist1(int i,int j)
{
    double x1,y1,x2,y2,x3,y3;
    x1=V[i].first,y1=V[i].second,x2=V[nxt[i]].first,y2=V[nxt[i]].second;
    x3=V[j].first,y3=V[j].second;
    return ((x2-x1)*(x3-(x1+x2)/2.0)+(y2-y1)*(y3-(y1+y2)/2.0))/sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}

double Dist3(int i,int j)
{
    double x1,y1,x2,y2,x3,y3;
    x1=V[i].first,y1=V[i].second,x2=V[nxt[i]].first,y2=V[nxt[i]].second;
    x3=V[j].first,y3=V[j].second;
    if(x1==x2)
        return abs(x3-x1);
    double m=(y1-y2)/(x1-x2);
    double n=(x1*y2-y1*x2)/(x1-x2);
    double d=(m*x3-y3+n)/sqrt(m*m+1);
    return abs(d);
}

bool comp(pair<double,double> a,pair<double,double> b)
{
    double x=det(P[0],a,b);
    if(x> mic)return 1;
    if(x<-mic)return 0;
    if(dist(P[0],a)-dist(P[0],b)>mic)return 0;
    return 1;
}

int main()
{
    f>>n;
    f>>P[0].first>>P[0].second;
    iq=0;
    for(i=1;i<n;i++)
    {
        f>>P[i].first>>P[i].second;
        if(P[i]<P[iq])
            iq=i;
    }
    swap(P[0],P[iq]);
    sort(P+1,P+n,comp);
    V[0]=P[0],V[1]=P[1],k=1;
    for(i=2;i<n;i++)
    {
        while(det(V[k-1],V[k],P[i])<-mic&&k)
            k--;
        V[++k]=P[i];
    }
    g<<k+1<<'\n';
    for(i=1;i<=k;i++)
        g<<fixed<<setprecision(10)<<V[i].first<<' '<<V[i].second<<'\n';
    g<<fixed<<setprecision(10)<<V[0].first<<' '<<V[0].second;
//    g<<dist;
//    for(i=0;i<k;i++)nxt[i]=i+1;nxt[k]=0;
//    pair<double,int> dst1={Dist1(0,0),0},dst2={Dist1(0,0),0},dst3={Dist3(0,0),0};
//    for(i=1;i<=k;i++)
//    {
//        dst1=max(dst1,{Dist1(0,i),i});
//        dst2=min(dst2,{Dist1(0,i),i});
//        dst3=max(dst3,{Dist3(0,i),i});
//    }
////    for(i=0;i<=k;i++)
////        g<<V[i].first<<' '<<V[i].second<<'\n';
//    double ans=(dst1.first-dst2.first)*dst3.first;
//    for(i=1;i<=k;i++)
//    {
////        g<<i-1<<' '<<dst1.second<<' '<<dst2.second<<' '<<dst3.second<<'\n';
//        dst1.first=Dist1(i,dst1.second);
//        dst2.first=Dist1(i,dst2.second);
//        dst3.first=Dist3(i,dst3.second);
//        double aux=Dist1(i,nxt[dst1.second]);
//        while(aux>dst1.first)
//        {
//            dst1={aux,nxt[dst1.second]};
//            aux=Dist1(i,nxt[dst1.second]);
//        }
//        aux=Dist1(i,nxt[dst2.second]);
//        while(aux<dst2.first)
//        {
//            dst2={aux,nxt[dst2.second]};
//            aux=Dist1(i,nxt[dst2.second]);
//        }
//        aux=Dist3(i,nxt[dst3.second]);
//        while(aux>dst3.first)
//        {
//            dst3={aux,nxt[dst3.second]};
//            aux=Dist3(i,nxt[dst3.second]);
//        }
//        ans=min(ans,(dst1.first-dst2.first)*dst3.first);
//    }
//    g<<ans;
    return 0;
}