Cod sursa(job #1547112)

Utilizator tudormaximTudor Maxim tudormaxim Data 9 decembrie 2015 00:53:44
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax = 805;
const int mmax = 60005;
struct point {double x, y;} v[nmax+mmax], a[mmax];

inline double sarrus(point a, point b, point c)
{
    return a.x*b.y + b.x*c.y + c.x*a.y - b.y*c.x - c.y*a.x - a.y*b.x;
}

inline bool cmp(point a, point b)
{
    return sarrus(v[1], a, b) > 0;
}
int main()
{
    ifstream fin ("poligon.in");
    ofstream fout ("poligon.out");
    int n, m, i, st[nmax+mmax], top=0, ind=1, ext;
    fin >>  n >> m;
    for(i=1; i<=n; i++)
    {
        fin >> v[i].x >> v[i].y;
        if(v[i].x < v[ind].x) ind=i;
    }
    for(i=1; i<=m; i++)
    {
        fin >> a[i].x >> a[i].y;
        v[n+i]=a[i];
    }
    swap(v[1], v[ind]);
    sort(v+2, v+n+m+1, cmp);
    v[n+m+1]=v[1];
    st[++top]=1;
    for(i=2; i<=n+m; i++)
    {
        st[++top]=i;
        while( sarrus(v[st[top-1]], v[st[top]], v[i+1]) < 0) top--;
    }
    ext=n+m-top;
    fout << m-ext;
    fin.close();
    fout.close();
    return 0;
}