高雄市98資訊學科能力競賽 第四題:在凸多邊型內或外
作法 : 做凸包
因為沒有人分享其他作法,所以在此提供複雜的做法
一直拉向量與其他的向量做單位向量的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
但對於一條線同側的兩點分別帶入方程後的正負號會相同。