本文主要是介绍poj 3335 3130 1279 判断是否有核，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Sample Input Sample Output
2 4 0 0 0 1 1 1 1 0 8 0 0 0 2 1 2 1 1 2 1 2 2 3 2 3 0
YES NO
题意：
顺时针给出n个点，求这个多边形是否有核，有就输出yes，否则输出no
题解：
套模板
多边形核的理解：在此多边形里面放一个摄像头，它可以扫到多边形的任意一个点
做法：半平面切割法。依次选择直线，然后和多边形交，然后剔除在外面的点，最后得到一个核区域或者点（形象的理解就像在削苹果）
poj 3335
#include<math.h>
#include<stdio.h>
#include<algorithm>
using namespace std;#define eps 1e-8
const int MAXN=10017;int n;
double r;
int cCnt,curCnt;///最终切割得到的多边形的顶点数、暂存顶点个数struct point
{double x,y;
};
point points[MAXN],p[MAXN],q[MAXN];///初始多边形顶点（顺时针）、最终切割后多边形顶点、暂存顶点void getline(point x,point y,double &a,double &b,double &c) ///两点x、y确定一条直线a、b、c为其系数
{a=y.y-x.y;b=x.x-y.x;c=y.x*x.y-x.x*y.y;
}
void initial()
{for(int i=1;i<=n;i++)p[i]=points[i];p[n+1]=p[1];p[0]=p[n];cCnt=n;
}
point intersect(point x,point y,double a,double b,double c)///点x、y所在直线与ax+by+c=0的交点
{double u=fabs(a*x.x+b*x.y+c);double v=fabs(a*y.x+b*y.y+c);point pt;pt.x=(x.x*v+y.x*u)/(u+v);pt.y=(x.y*v+y.y*u)/(u+v);return pt;
}
void cut(double a,double b ,double c)
{curCnt=0;for(int i=1;i<=cCnt;i++){if(a*p[i].x+b*p[i].y+c>=0)///点代入线都大于0，说明此点都在这条直线某一边，不用切q[++curCnt]=p[i];else{if(a*p[i-1].x+b*p[i-1].y+c>0)///如果p[i-1]在直线的右侧的话q[++curCnt]=intersect(p[i],p[i-1],a,b,c);if(a*p[i+1].x+b*p[i+1].y+c>0)q[++curCnt]=intersect(p[i],p[i+1],a,b,c);}}for(int i=1;i<=curCnt;i++)p[i]=q[i];p[curCnt+1]=q[1];p[0]=p[curCnt];cCnt=curCnt;
}
void solve()
{///注意：默认点是顺时针initial();double a,b,c;for(int i=1;i<=n;i++){getline(points[i],points[i+1],a,b,c);cut(a,b,c);}
}int main()
{int T;//freopen("in.txt","r",stdin);scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lf%lf",&points[i].x,&points[i].y);points[n+1]=points[1];solve();puts(cCnt<1?"NO":"YES");}return 0;
}
poj 3130
#include<math.h>
#include<stdio.h>
#include<algorithm>
using namespace std;#define eps 1e-8
const int MAXN=10017;int n;
double r;
int cCnt,curCnt;///最终切割得到的多边形的顶点数、暂存顶点个数struct point
{double x,y;
};
point points[MAXN],p[MAXN],q[MAXN];///初始多边形顶点（顺时针）、最终切割后多边形顶点、暂存顶点void getline(point x,point y,double &a,double &b,double &c) ///两点x、y确定一条直线a、b、c为其系数
{a=y.y-x.y;b=x.x-y.x;c=y.x*x.y-x.x*y.y;
}
void initial()
{for(int i=1;i<=n;i++)p[i]=points[i];p[n+1]=p[1];p[0]=p[n];cCnt=n;
}
point intersect(point x,point y,double a,double b,double c)///点x、y所在直线与ax+by+c=0的交点
{double u=fabs(a*x.x+b*x.y+c);double v=fabs(a*y.x+b*y.y+c);point pt;pt.x=(x.x*v+y.x*u)/(u+v);pt.y=(x.y*v+y.y*u)/(u+v);return pt;
}
void cut(double a,double b ,double c)
{curCnt=0;for(int i=1;i<=cCnt;i++){if(a*p[i].x+b*p[i].y+c>=0)///点代入线都大于0，说明此点都在这条直线某一边，不用切q[++curCnt]=p[i];else{if(a*p[i-1].x+b*p[i-1].y+c>0)///如果p[i-1]在直线的右侧的话q[++curCnt]=intersect(p[i],p[i-1],a,b,c);if(a*p[i+1].x+b*p[i+1].y+c>0)q[++curCnt]=intersect(p[i],p[i+1],a,b,c);}}for(int i=1;i<=curCnt;i++)p[i]=q[i];p[curCnt+1]=q[1];p[0]=p[curCnt];cCnt=curCnt;
}
void solve()
{///注意：默认点是顺时针initial();double a,b,c;for(int i=1;i<=n;i++){getline(points[i],points[i+1],a,b,c);cut(a,b,c);}
}
void GuiZhengHua()
{///规整化方向，逆时针变顺时针，顺时针变逆时针for(int i=1;i<=n;i++) q[i]=points[n-i+1];for(int i=1;i<=n;i++) points[i]=q[i];
}
int main()
{//freopen("in.txt","r",stdin);while(scanf("%d",&n)&&n){for(int i=1;i<=n;i++)scanf("%lf%lf",&points[i].x,&points[i].y);GuiZhengHua();points[n+1]=points[1];solve();puts(cCnt<1?"0":"1");}return 0;
}
poj 1279 计算内核面积
#include<math.h>
#include<stdio.h>
#include<algorithm>
using namespace std;#define eps 1e-8
const int MAXN=2000;int n;
int cCnt,curCnt;///最终切割得到的多边形的顶点数、暂存顶点个数struct point
{double x,y;
};
point points[MAXN],p[MAXN],q[MAXN];///初始多边形顶点（顺时针）、最终切割后多边形顶点、暂存顶点void getline(point x,point y,double &a,double &b,double &c) ///两点x、y确定一条直线a、b、c为其系数
{a=y.y-x.y;b=x.x-y.x;c=y.x*x.y-x.x*y.y;
}
void initial()
{for(int i=1;i<=n;i++)p[i]=points[i];p[n+1]=p[1];p[0]=p[n];cCnt=n;
}
point intersect(point x,point y,double a,double b,double c)///点x、y所在直线与ax+by+c=0的交点
{double u=fabs(a*x.x+b*x.y+c);double v=fabs(a*y.x+b*y.y+c);point pt;pt.x=(x.x*v+y.x*u)/(u+v);pt.y=(x.y*v+y.y*u)/(u+v);return pt;
}
void cut(double a,double b ,double c)
{curCnt=0;for(int i=1;i<=cCnt;i++){if(a*p[i].x+b*p[i].y+c>=0)///点代入线都大于0，说明此点都在这条直线某一边，不用切q[++curCnt]=p[i];else{if(a*p[i-1].x+b*p[i-1].y+c>0)///如果p[i-1]在直线的右侧的话q[++curCnt]=intersect(p[i],p[i-1],a,b,c);if(a*p[i+1].x+b*p[i+1].y+c>0)q[++curCnt]=intersect(p[i],p[i+1],a,b,c);}}for(int i=1;i<=curCnt;i++)p[i]=q[i];p[curCnt+1]=q[1];p[0]=p[curCnt];cCnt=curCnt;
}
double solve()
{///注意：默认点是顺时针initial();double a,b,c;for(int i=1;i<=n;i++){getline(points[i],points[i+1],a,b,c);cut(a,b,c);}double area=0;for(int i=1;i<=curCnt;i++)area+=p[i].x*p[i+1].y-p[i+1].x*p[i].y;return fabs(area/2.0);
}int main()
{int T;//freopen("in.txt","r",stdin);scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lf%lf",&points[i].x,&points[i].y);points[n+1]=points[1];printf("%.2lf\n",solve());}return 0;
}
这篇关于poj 3335 3130 1279 判断是否有核的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
