Cod sursa(job #37977)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 25 martie 2007 13:12:35
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

#define maxn 1010
#define db double
#define eps 0.000001
#define pb push_back

int n,m,l;
int a[maxn],b[maxn],c[maxn];
int x[maxn],y[maxn];
db x2[maxn],y2[maxn];
int p[maxn],p2[maxn];
vector <int> s;
set < vector <int> > h;

int cmp(int i,int j)
{
    return (y2[i]+eps<=y2[j]) || ((fabs(y2[j]-y2[i])<eps) && (x2[i]<x2[j]));
}

int cmp2(int i,int j)
{
    return (y2[i]-eps>=y2[j]) || ((fabs(y2[j]-y2[i])<eps) && (x2[i]>x2[j]));
}

db cross(db x1,db x2,db x3,db y1,db y2,db y3)
{
	return (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1);
}

void hull()
{
     int i;
     db aux;
     
     l=2;
     p2[1]=p[1];
     p2[2]=p[2];
     
	 for (i=3;i<=n;i++)
	 {
		 aux=cross(x2[p2[l-1]],x2[p2[l-1]],x2[p[i]],y2[p2[l-1]],y2[p2[l]],y2[p[i]]);

		 while ((aux<=0) && (l>=2))
		 {
			   l--;
			   aux=cross(x2[p2[l-1]],x2[p2[l]],x2[p[i]],y2[p2[l-1]],y2[p2[l]],y2[p[i]]);
		 }

		 l++;
		 p2[l]=p[i];
	 }
}

void convex()
{
     int i;
     for (i=1;i<=n;i++) p[i]=i;
     sort(p+1,p+n+1,cmp);
     
     hull();
     s.clear();
     
     for (i=1;i<=l;i++) s.pb(p2[i]);
     
     for (i=1;i<=n;i++) p[i]=i;
     
     sort(p+1,p+n+1,cmp2);
     hull();
     
     for (i=2;i<l;i++) s.pb(p2[i]);
     
     sort(s.begin(),s.end());
     
     h.insert(s);
}

int main()
{
    freopen("regiuni.in","r",stdin);
    freopen("regiuni.out","w",stdout);
    
    int i,j;
    db x3,y3,x1,y1;
    scanf("%d %d ",&n,&m);
    
    for (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 (i=1;i<=m;i++) scanf("%d %d ",&x[i],&y[i]);
    
    for (i=1;i<=m;i++)
    {
        for (j=1;j<=n;j++)
        {
            x1=1;
            x3=2;
            if (b[j]!=0) 
            {
                y1=db((-c[j]-a[j]*x1)/b[j]);
                y3=db((-c[j]-a[j]*x3)/b[j]);
            }
            else 
            {
                 y1=db((-c[j]-a[j]*x1)/eps);
                 y3=db((-c[j]-a[j]*x3)/eps);
            }            
            
            x1-=x[i];
            y1-=y[i];
            x3-=x[i];
            y3-=y[i];
            double a1 = y3 - y1;
            db b1=x1-x3;
            db c1=x1*a1+y1*b1*(-1);
            x2[j]=db(a1/c1);
            y2[j]=db(b1/c1);            
        }
        
        convex();                        //fac convex hull        
    }
    
    printf("%d\n",h.size());
    
    return 0;
}