Cod sursa(job #154696)

Utilizator p1ccolinoAlexandru Vlad p1ccolino Data 11 martie 2008 13:18:01
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb
#include<fstream.h>
float x[11],y[11],xp,yp;
int p[11],n,i,s[11],m,contur,cresc;
int nr=0,capat=0,j;
float panta (int i)  // panta PiPi+1
{ return (y[i+1]-y[i])/(x[i+1]-x[i]);}

int apartine(float X,float Y,int i)
{ //(x,y) se gaseste pe segmentul PiPi+1
   if((x[i+1]-x[i])*(Y-y[i])==(X-x[i])*(y[i+1]-y[i]) &&
       (x[i]<=X && X<=x[i+1] || x[i+1]<=X && X<=x[i])) return 1;
    return 0;
}

int main()
{float X,Y;
ifstream f("poligon.in");
ofstream g("poligon.out");
f>>n>>m;
for(i=0;i<n;i++) f>>x[i]>>y[i];
x[n]=x[0];y[n]=y[0];

for(j=0;j<n;j++)
{f>>xp>>yp;
contur=0;nr=0;
if(xp||yp)
 			{for(i=0;i<n+1 && contur==0;i++) if(apartine(xp,yp,i)) contur=1;
 						if(contur==1) 		g<<"pe contur ,in interior";
  						else {
  								if(xp) {//consideram semidreapta  Y=yp/xp*X cu X>xp
											for(i=0;i<n;i++)
		   														if(xp*(y[i+1]-y[i])!=yp*(x[i+1]-x[i]))   //= nu sunt paralele
		      																		{ // se intersecteaza dreptele suport in (X,Y)
																							X=(y[i]-x[i]*panta(i))/(yp/xp-panta(i));
																				 			Y=X*yp/xp;
                                                                     if(X>xp && (x[i]<=X && X<=x[i+1] || x[i+1]<=X && X<=x[i]))
																							  nr++;
			// vad daca este capat
																						  	if(X==x[i] && Y==y[i] || X==x[i+1] && Y==y[i+1])capat++;
																				      }
											  		   			else
                                                   		{ //vad daca (xp,yp)se gaseste pe PiPi+1
			   																 if((x[i+1]-x[i])*(yp-y[i])==(xp-x[i])*(y[i+1]-y[i]) && x[i]>xp)
				   															    nr++;
																			  }
										    nr=nr-capat/2;
          				  			}
          // pt xp=0
             				else if(yp){//consideram semid X=xp/yp*Y cu Y>yp
      												 X=0;
   												for(i=0;i<n;i++)
      										if(yp*(x[i+1]-x[i])!=0) // nu sunt paralele
                                    		{//se intersect dreptele suport in (X,Y)
       													Y=(y[i]-x[i]*panta(i));
													       if(Y>yp &&(y[i]<=Y&&Y<=y[i+1] || y[i+1]<=Y &&Y<=y[i]))
														       nr++;
														       //vad daca este capat
														        	if(X==x[i] && Y==y[i] || X==x[i+1] && Y==y[i+1])capat++;
										            }
       									   else
										         	if((x[i+1]-x[i])*(yp-y[i])==(xp-x[i])*(y[i+1]-y[i]) && y[i]>yp)
																     nr++;

		    										nr=nr-capat/2;
                                     }
                        }
           }
           //(xp,yp)=(0,0)
 else {
 		for(i=0;i<n;i++)
      	{if(x[i+1]!=x[i]) // nu sunt paralele
         	{//se intersecteaza
              if(y[i]-x[i]*panta(i)==0) nr++;
             Y=X=1;
       if(Y>yp &&(y[i]<=Y&&Y<=y[i+1] || y[i+1]<=Y &&Y<=y[i]))
       nr++;
       //vad daca este capat
       	if(X==x[i] && Y==y[i] || X==x[i+1] && Y==y[i+1])capat++;
            }
         else
         	if((x[i+1]-x[i])*(yp-y[i])==(xp-x[i])*(y[i+1]-y[i]) && y[i]>yp)
				     nr++;

		    nr=nr-capat/2;}
         }


if(nr%2==0) m--;
}
g<<m<<"\n";
f.close();
g.close();
return 0;
}