本文主要是介绍HDU 4353 Finding Mine（做法经典 三角形内部点/面积），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4353
这个题目做法好啊，我想了好久都没做出来，后来看了解题报告^_^
这个题目首先按照x值排序，之后枚举所有三角形
最后的步骤就是求出在三角形中的点的个数
也就是求出点的个数是经典的
这个还是要联系程序来讲
点在最长边上面的减去点在其他两条边上面的，注意要取绝对值就是在三角形中的点
注意这个在上面指的是左边的点画一条垂线，右边的点画一条直线，在两条垂线之间
的和在此线段上面的点！
具体为什么会是这样自己在纸上画画就知道了！
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
#define MIN(a,b) (a<b?a:b)
#define maxn 600
int seg[maxn][maxn],n,m;
struct point{double x,y;
}mine[maxn],po[maxn];
bool cmp(const point &a,const point &b){if(a.x == b.x) return a.y < b.y;return a.x < b.x;
}
double cross(const point &a,const point &b,const point &c){return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
int main(){int i,j,k,t,temp,Case=0;double ans=-1;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(i=0;i<n;i++)scanf("%lf%lf",&po[i].x,&po[i].y);for(i=0;i<m;i++)scanf("%lf%lf",&mine[i].x,&mine[i].y);sort(po,po+n,cmp);memset(seg,0,sizeof(seg));for(i=0;i<n;i++)for(j=i+1;j<n;j++)for(k=0;k<m;k++){if(mine[k].x >= po[i].x && mine[k].x < po[j].x && cross(po[i],po[j],mine[k]) > 0)seg[i][j]++;}ans=-1;for(i=0;i<n;i++)for(j=i+1;j<n;j++)for(k=j+1;k<n;k++){temp=abs(seg[i][k]-seg[i][j]-seg[j][k]);if(temp == 0) continue;if(ans == -1) ans=fabs(cross(po[i],po[j],po[k])/2)/temp;else ans=MIN(ans,fabs(cross(po[i],po[j],po[k])/2)/temp);}if(ans==-1) printf("Case #%d: -1\n",++Case);else printf("Case #%d: %.6f\n",++Case,ans);}return 0;
}
这篇关于HDU 4353 Finding Mine（做法经典 三角形内部点/面积）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
