http://poj.org/problem?id=3335

题目大意:给按照顺时针序的多边形顶点,问其是否有内核。

——————————————————————————————

看了两个小时的资料,对板子敲了一个小时,终于将简单的板子题弄过了。

(原本计划去搞风水那道题,但发现我等级的太低了……需要从基础练起半平面交)

代码参考:http://blog.csdn.net/accry/article/details/6070621

理解参考:http://blog.csdn.net/acm_zl/article/details/11153475

(这个理解参考找了很久……我只看得懂这个,先看下面的再看上面的能对理解起到蛮好的帮助)

#include<cstdio>
#include<queue>
#include<cctype>
#include<cstring>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double dl;
const dl eps=1e-;
const int N=;
struct Point{
dl x;
dl y;
}p[N],point[N],q[N],z;
//point,初始点
//q,暂时存可行点
//p,记录可行点
int n,curcnt,cnt;
//curcnt,暂时存可行点个数
//cnt,记录可行点个数
inline Point getmag(Point a,Point b){
Point s;
s.x=b.x-a.x;s.y=b.y-a.y;
return s;
}
inline dl multiX(Point a,Point b){
return a.x*b.y-b.x*a.y;
}
inline void getline(Point x,Point y,dl &a,dl &b,dl &c){
a=y.y-x.y;
b=x.x-y.x;
c=y.x*x.y-x.x*y.y;
return;
}
inline Point intersect(Point x,Point y,dl a,dl b,dl c){
Point s;
dl u=fabs(a*x.x+b*x.y+c);
dl v=fabs(a*y.x+b*y.y+c);
s.x=(x.x*v+y.x*u)/(u+v);
s.y=(x.y*v+y.y*u)/(u+v);
return s;
}
inline void cut(dl a,dl b,dl c){
curcnt=;
for(int i=;i<=cnt;i++){
if(a*p[i].x+b*p[i].y+c>-eps)q[++curcnt]=p[i];
else{
if(a*p[i-].x+b*p[i-].y+c>eps){
q[++curcnt]=intersect(p[i],p[i-],a,b,c);
}
if(a*p[i+].x+b*p[i+].y+c>eps){
q[++curcnt]=intersect(p[i],p[i+],a,b,c);
}
}
}
for(int i=;i<=curcnt;i++)p[i]=q[i];
p[curcnt+]=p[];p[]=p[curcnt];
cnt=curcnt;
return;
}
inline void init(){
for(int i=;i<=n;i++)p[i]=point[i];
z.x=z.y=;
p[n+]=p[];
p[]=p[n];
point[n+]=point[];
cnt=n;
return;
}
inline void regular(){//调换方向
for(int i=;i<(n+)/;i++)swap(point[i],point[n-i]);
return;
}
inline bool solve(){
//注意:默认点是顺时针,如果题目不是顺时针,规整化方向
init();
for(int i=;i<=n;i++){
dl a,b,c;
getline(point[i],point[i+],a,b,c);
cut(a,b,c);
}
return cnt;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%lf%lf",&point[i].x,&point[i].y);
}
if(!solve())puts("NO");
else puts("YES");
}
return ;
}

最新文章

  1. Enterprise Solution 企业资源计划管理软件 C/S架构,支持64位系统,企业全面应用集成,制造业信息化
  2. android多分辨率多密度下界面适配方案
  3. C# 静态方法和非静态方法
  4. LeetCode.4 两个有序数组的中位数问题
  5. 【循序渐进学Python】7.面向对象的核心——类型(上)
  6. NDK、SDK以及JNI的关系
  7. String类及常用方法
  8. Testing and Checking Refined
  9. 输出string vector到file
  10. tinyxml2简单使用
  11. C++第一天学习
  12. Dagger2源码浅析
  13. Django的认证系统
  14. JDBC——Java语言连接数据库的标准
  15. webAPP如何实现移动端拍照上传(Vue组件示例)?
  16. vue-amap 实例获取与自动缩放
  17. Spring技术内幕_IOC容器载入Bean定义资源文件
  18. 基于jQuery垂直多级导航菜单代码
  19. Day 36 网络编程-计算机的发展
  20. 控制HttpContext为null

热门文章

  1. onenet基础通信套件加B300移植
  2. SSH项目中的困惑之一
  3. hdu1394Minimum Inversion Number(线段树,求最小逆序数)
  4. Qt PC 安卓 tcp传输文件
  5. 域名添加www之后(或域名后加端口)无法访问(阿里云服务器)
  6. TW实习日记:第20-21天
  7. 【forEach控制器】-(针对,在不知道取到得参数有多少?但是要全部执行每一条的情况)
  8. 【转】《王者荣耀》技术总监复盘回炉历程:没跨过这三座大山,就是另一款MOBA霸占市场了
  9. 理解 JavaScript 原型 / 原型链
  10. 2.安装hdfs yarn