題目：Finding Mine

?

題意：給你n個(gè)點(diǎn)，m個(gè)金礦點(diǎn)，找一個(gè)多邊形，使得多邊形的面積除以這個(gè)多邊形內(nèi)的金礦點(diǎn)個(gè)數(shù)的比值最小。

思路：其實(shí)就是找一個(gè)比值最小的三角形就行了，因?yàn)槠渌娜切蔚谋戎刀急人?#xff0c;組合成多邊形后勢(shì)必會(huì)將比值變大。可以簡(jiǎn)短的證明的。

#include <iostream> #include <string.h> #include <stdio.h> #include <math.h> #include <algorithm>using namespace std;struct Point {int x,y;bool operator<(const Point &cmp) const{return x<cmp.x;} };Point p[210]; Point mine[510];int cross(Point A,Point B,Point C) {return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x); }int n,m; int num[210][510];void Init(Point a,Point b,int &cnt) {int x1=a.x;int x2=b.x;for(int i=0;i<m;i++)if(x1<=mine[i].x&&mine[i].x<x2)if(cross(a,b,mine[i])>0)cnt++; }int main() {int t,cas=1;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%d%d",&p[i].x,&p[i].y);sort(p,p+n);for(int i=0;i<m;i++)scanf("%d%d",&mine[i].x,&mine[i].y);for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)Init(p[i],p[j],num[i][j]=0);double ans=-1;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){for(int k=j+1;k<n;k++){int cnt=num[i][k]-num[i][j]-num[j][k];if(cnt==0) continue;double area=cross(p[i],p[j],p[k])/2.0;double tmp=fabs(area/cnt);if(ans==-1||tmp<ans) ans=tmp;}}}printf("Case #%d: ",cas++);if(ans==-1) puts("-1");else printf("%.6lf\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU4353(找一个三角形面积与它里面包含点的比值最小)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。