Cod sursa(job #1592856)

Utilizator AeroHHorea Stefan AeroH Data 8 februarie 2016 00:37:08
Problema Puteri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
#define punct pair<int,int>
#define x first
#define y second
using namespace std;

ifstream f(".in");
ofstream g(".out");
vector<punct> P,Q,R;
int d(punct a,punct b){
    return (a.x*b.y-a.y*b.x);
}
bool sdet(punct a,punct b,punct c){
    return d(a,b)+d(b,c)+d(c,a)>0;
}
bool isin(punct P,vector<punct> A){
    bool t=sdet(A.back(),A[0],P);
    for(int i=0;i<A.size()-1;++i)
        if(sdet(A[i],A[i+1],P)!=t)
            return 0;

    return 1;
}
void make(){
    int i;
    for(i=0;i<P.size();++i)if(isin(P[i],Q))R.push_back(P[i]);
    for(i=0;i<Q.size();++i)if(isin(Q[i],P))R.push_back(Q[i]);
    sort(R.begin(),R.end());
    R.resize(unique(R.begin(),R.end())-R.begin());

}
void melk()
{
    if (R.size()<3)g<<0,exit(0);
    deque<punct> D;
    D={R[0],R[1],R[2],R[0]};
    for(int i=3;i<R.size();++i)
    {
        while(!sdet(D[0],D[1],R[i]))D.pop_back();
        while(!sdet(D[D.size()-2],D.back(),R[i]))D.pop_back();
        D.push_back(R[i]);D.push_front(R[i]);
    }
    double a=0;
    for (int i=0;i<D.size();++i)
        a=a+d(D[i],D[i+1]);
    a=abs(a/2);
    g<<a;
}
int main()
{
    int N,x,y;
    f>>N;while(N--)f>>x>>y,P.push_back({x,y});
    f>>N;while(N--)f>>x>>y,Q.push_back({x,y});
    make();
    melk();

    return 0;
}