Cod sursa(job #37535)

Utilizator alextheroTandrau Alexandru alexthero Data 25 martie 2007 10:47:35
Problema Regiuni Scor 10
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasa a 10-a Marime 2.83 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <set>
#include <vector>

#define nmax 1015
#define mmax 1015
#define pb push_back

using namespace std;

int a[nmax],b[nmax],c[nmax],place[nmax],ppx,ppy,n,m,P,st[nmax];
double px[nmax],py[nmax],ptx[nmax],pty[nmax],vx,vy;
vector <int> v;
set < vector<int> > h;

double sqr(double x) {
    return x*x;
}

double dist(double x,double y) {
    return sqrt((double)sqr(x)+(double)sqr(y));
}

double dist(double x1,double y1,double x2,double y2) {
    return sqrt(sqr(x1-x2)+sqr(y1-y2));
}

double cp(int p1,int p2,int p3) {
    return (ptx[p2]-ptx[p1])*(pty[p3]-pty[p2])-(ptx[p3]-ptx[p2])*(pty[p2]-pty[p1]);
}

int cmp(int i,int j) {
    double x1=atan2(pty[i]-vy,ptx[i]-vx);
    double x2=atan2(pty[j]-vy,ptx[j]-vx);
    if(x1>x2) return 0;
    else if(x1==x2) {
        if(dist(ptx[i]-vx,pty[i]-vy)>dist(ptx[j]-vx,pty[i]-vy)) return 0;
        else return 1;
    }   
    else return 1;

}

int main() {
    freopen("regiuni.in","r",stdin);
    freopen("regiuni.out","w",stdout);

    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
    a[n + 1] = 1;
    b[n + 1] = 0;
    c[n + 1] = 30001;

    a[n + 2] = 1;
    b[n + 2] = 0;
    c[n + 2] = -30001;

    a[n + 3] = 0;
    b[n + 3] = 1;
    c[n + 3] = -30001;

    a[n + 4] = 0;
    b[n + 4] = 1;
    c[n + 4] = 30001;

    n += 4;

    for(int i = 1; i <= m; i++) {
        scanf("%d%d",&ppx,&ppy);
        for(int j = 1; j <= n; j++) {
            double x1 = 1;
            double x2 = 2;
            double y1 = (-c[j] - a[j] * x1) / (b[j] != 0 ? b[j] : 0.01);
            double y2 = (-c[j] - a[j] * x2) / (b[j] != 0 ? b[j] : 0.01);
            x1 -= ppx; x2 -= ppx;
            y1 -= ppy; y2 -= ppy;
            double a1 = y2 - y1;
            double b1 = x1 - x2;
            double c1 = (x1 * a1 + y1 * b1) * -1;
            ptx[j] = (double)a1 / c1;
            pty[j] = (double)b1 / c1;
        }

        int P = 1;
        for(int j = 1; j <= n; j++) {
            place[j] = j;
            if(pty[j] < pty[P] || (pty[j] == pty[P] && ptx[i] < ptx[P])) P = j;
        }

        vx = (double)ptx[P]; vy = (double)pty[P];
        sort(place + 1,place + n + 1,cmp);

        st[0] = 0;
        st[++st[0]] = place[1];
        st[++st[0]] = place[2];
        for(int j = 3; j <= n; j++) {
            double o = cp(st[st[0] - 1],st[st[0]],place[j]);
            while(o <= 0 && st[0] >= 2) {
                st[0] --;
                o = cp(st[st[0] - 1],st[st[0]],place[j]);
            }
            st[++st[0]] = place[j];
        }

        v.clear();
        for(int j = 1; j <= st[0]; j++) v.pb(st[j]);
        sort(v.begin(),v.end());

        h.insert(v);
    }
    printf("%d\n",h.size());
 
    return 0;
}