摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 做凸包

因為沒有人分享其他作法,所以在此提供複雜的做法

一直拉向量與其他的向量做單位向量的MIN OR　MAX

/**************************************************************/

#include<stdlib.h>
#include<stdio.h>
#include<math.h>
int N,a,P[100][2],M[100][2];
int area(int top)
{
   int SUM=0;
   int a;
   for(a=1;a<=top;a++)
       SUM=SUM+(M[a][0]*M[a+1][1])-(M[a][1]*M[a+1][0]);
   return SUM;
}
int ConvexHull(int N)
{
   int a,b,sx,sy=1000,used[100]={0},un;
   for(a=1;a<=N;a++)
      if(P[a][1]<sy) sx=P[a][0],sy=P[a][1],un=a;
   M[0][0]=1000,M[0][1]=sy; /*遠處的一點*/
   M[1][0]=sx,M[1][1]=sy;/*起點*/
 /*  printf("(%d,%d)\n",M[1][0],M[1][1]);*/
   for(a=1;a<=N+2;a++) /*最多的周圍點*/
      {
          int tx=M[a][0]-M[a-1][0],ty=M[a][1]-M[a-1][1]; /*向量AB*/
          int next;
          double MAX=-2147483647;
           for(b=1;b<=N;b++)
              if(used[b]==0)
                {
                   int px=P[b][0]-M[a][0],py=P[b][1]-M[a][1];/*向量BC*/
                   if(px*px+py*py==0) continue;
                   double pxy=sqrt(px*px+py*py);  /*單位向量化*/
                   double temp=tx*px/pxy+ty*py/pxy;/*AB內積BC*/
                   if(temp>MAX) MAX=temp,next=b;
                }
           M[a+1][0]=P[next][0],M[a+1][1]=P[next][1];
           used[next]=1;
         /*  printf("(%d,%d) %d %d %lf\n",P[next][0],P[next][1],tx,ty,MAX); */
           if(next==un) break;
      }
   /*printf("--------------------\n");*/
   return area(a);
}
main()
{ 
  while(scanf("%d",&N)==1)
      {
        for(a=1;a<=N+1;a++)
           scanf("%d,%d",&P[a][0],&P[a][1]);
        int area=ConvexHull(N);
        int test=ConvexHull(N+1);
        if(area==test) printf("IN\n");
        else printf("OUT\n");
      }
  return 0;
}

/***********************************************************/

***

以下是文炫所提供的作法   由於我也不太懂,所以有問題  無法立即回答

/***********************************************************/

#include <stdio.h>  
int t[53][2]={},n,px,py,flag=1;  
int cp(int a,int b,int c,int x,int y)/*運算點帶入線方程為大於0或小於0*/
{  
    int d=a*x+b*y+c;  
    if(d>=0)return 1;  
    return 0;  
}  
int check(int p) /*看要檢查的點是否與多邊型頂點有相同的正負號*/
{  
    int a=(t[p][1]-t[p+1][1]),b=t[p+1][0]-t[p][0],c=t[p][0]*t[p+1][1]-t[p+1][0]*t[p][1];  
    int k=cp(a,b,c,t[p+2][0],t[p+2][1])^cp(a,b,c,px,py);  
    return k;  
}  
void che()   /*檢查所有線，一旦有錯就return*/
{  
     int i;  
     for(i=0;i<n;i++)  
     if(check(i)){flag=0;return;}  
}  
int main()  
{  
    int i;  
    while(scanf("%d",&n)==1)  
    {  
        flag=1;  
        for(i=0;i<n;i++)  
        scanf("%d,%d",&t[i][0],&t[i][1]);  
        t[n][0]=t[0][0],t[n][1]=t[0][1],t[n+1][0]=t[1][0],t[n+1][1]=t[1][1];  
        scanf("%d,%d",&px,&py);   /*要檢查的點*/
        che();  
        if(flag)printf("IN\n");  
        else printf("OUT\n");  
    }  
    return 0;  
}


應用的理論就是
對於一條線方程式ax+by+c=0
將不在線上的點(x0,y0)帶入方程得到ax0+by0+c，此值可能大於0可能小於0
但對於一條線同側的兩點分別帶入方程後的正負號會相同。