HDUOJ---(4708)Herding

Herding

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 937    Accepted Submission(s): 254

Problem Description

Little John is herding his father's cattles. As a lazy boy, he cannot tolerate chasing the cattles all the time to avoid unnecessary omission. Luckily, he notice that there were N trees in the meadow numbered from 1 to N, and calculated their cartesian coordinates (Xi, Yi). To herding his cattles safely, the easiest way is to connect some of the trees (with different numbers, of course) with fences, and the close region they formed would be herding area. Little John wants the area of this region to be as small as possible, and it could not be zero, of course.

Input

The first line contains the number of test cases T( T<=25 ). Following lines are the scenarios of each test case. The first line of each test case contains one integer N( 1<=N<=100 ). The following N lines describe the coordinates of the trees. Each of these lines will contain two float numbers Xi and Yi( -1000<=Xi, Yi<=1000 ) representing the coordinates of the corresponding tree. The coordinates of the trees will not coincide with each other.

Output

For each test case, please output one number rounded to 2 digits after the decimal point representing the area of the smallest region. Or output "Impossible"(without quotations), if it do not exists such a region.

Sample Input

1

4

-1.00 0.00

0.00 -3.00

2.00 0.00

2.00 2.00

Sample Output

2.00

Source

2013 ACM/ICPC Asia Regional Online —— Warmup

Recommend

liuyiding

几何题,可以采用海伦公式,或者行列式

其中海伦公式为:sqrt(l-a)*(l-b)*(l-c)----》个人觉得此处做起来麻烦。。。

所以果断采用行列式....但需要注意精度问题....不然会错很多次的...lz就因为此wa20余次.....说出来都是泪..

代码:

 1     #include<iostream>
 2     #include<cstdio>
 3     #include<cstring>
 4     #include<cmath>
 5     #define maxn 1e10
 6     using namespace std;
 7     double area(double *a,double *b,double *c)    //运用行列式求面积
 8     {
 9        double temp=(a[0]*b[1]+a[1]*c[0]+b[0]*c[1])-(c[0]*b[1]+b[0]*a[1]+a[0]*c[1]);
10         return temp<0? -temp:temp;
11     }
12     int main()
13     {
14         double point[105][2],ans;
15          int t,n,i,j,k;
16             scanf("%d",&t);
17         while(t--)
18         {
19           scanf("%d",&n);
20           for(i=0;i<n;i++)
21               scanf("%lf%lf",&point[i][0],&point[i][1]);
22             ans=maxn;
23           for(i=0 ; i<n-2; i++ )
24           {
25               for(j=i+1;j<n-1;j++)
26               {
27                   for(k=j+1;k<n;k++)
28                   {
29                     double temp=area(point[i],point[j],point[k])/2.0;    
30                     if(ans>temp&&temp>1e-8)
31                                 ans=temp;
32                   }
33               }
34           }
35           if(n<3||ans<1e-4||ans==maxn)  
36               printf("Impossible\n");
37           else
38           printf("%.2lf\n",ans);     
39         }
40         return 0;
41     }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

HDUOJ----(1031)Design T-Shirt

Design T-Shirt Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/327...

377130
来自专栏ml

HDUOJ-----1085Holding Bin-Laden Captive!

Holding Bin-Laden Captive! Time Limit: 2000/1000 MS (Java/Others)    Memory Limi...

286110
来自专栏ml

HDUOJ-------2493Timer(数学 2008北京现场赛H题)

Timer Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

27640
来自专栏ml

HDUOJ----Good Numbers

Good Numbers Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768...

32060
来自专栏WindCoder

Declarative Programming: Is It A Real Thing?

由于合作方希望能以英文形式发布,故以后top的译文看时间而定,没时间就不再尝试翻译(而且本来水平也不咋地),仅保留原文于此。本次是一篇关于声明式编程的讨论文章,...

10710
来自专栏pangguoming

Node.js 开发模式(设计模式)

Asynchronous code & Synchronous code As we have seen in an earlier post (here), ...

32870
来自专栏别先生

Caused by: java.net.ConnectException: Connection refused: master/192.168.3.129:7077

1:启动Spark Shell,spark-shell是Spark自带的交互式Shell程序,方便用户进行交互式编程,用户可以在该命令行下用scala编写spa...

1K60
来自专栏ml

HDUOJ-------Naive and Silly Muggles

Naive and Silly Muggles Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: ...

33860
来自专栏数据结构与算法

BZOJ1053: [HAOI2007]反素数ant(爆搜)

  对于任何正整数x,其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足:g(x)>g(i) 0<i<x

10920
来自专栏ml

poj-------(2240)Arbitrage(最短路)

Arbitrage Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 156...

39280

扫码关注云+社区

领取腾讯云代金券