POJ 3301 Texas Trip (三分求极限）

本文主要是介绍POJ 3301 Texas Trip (三分求极限），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给出许多点的坐标，用最小的正方形覆盖之。

题解：三分。注意精度····。公式神马的画个图推一下即解决

double mid1 = (left + right)/2;             

double mid2 = (mid1 + right)/2;         

相比 

double mid1 =left +(right - left)/3;
double mid2 = right - (right - left)/3;
要求更高的精度。

 

#include <cmath>
#include <iostream>
using namespace std;
#define MAX 33
#define eps 0.00000005
#define max(a,b) (a>b?a:b)
struct { double x, y; } p[MAX];
double cal1 ( int n, double d )
{
double dis1 = 0.0, temp;
for ( int i = 1; i < n; i++ )
{
for ( int j = i + 1; j <= n; j++ )
{
temp = fabs( (p[i].y-p[j].y) * sin(d) + (p[i].x-p[j].x) * cos(d));
dis1 = max ( dis1, temp );
}
}
return dis1;
}
double cal2 ( int n, double d )
{
double dis2 = 0.0, temp;
for ( int i = 1; i < n; i++ )
{
for ( int j = i + 1; j <= n; j++ )
{
temp = fabs( (p[i].y-p[j].y) * cos(d) - (p[i].x-p[j].x) * sin(d));
dis2 = max ( dis2, temp );
}
}
return dis2;
}
int main()
{
int cs, n;
scanf("%d",&cs); 
while ( cs-- )
{
scanf("%d",&n);
for ( int i = 1; i <= n; i++ )
scanf("%lf%lf", &p[i].x, &p[i].y);
double ans = 1000, low = 0, high = asin(1.0);
while ( high - low > eps )
{  
double mid1 = low + ( high - low ) / 3;
double mid2 = high - ( high - low ) / 3;
double len1 = max ( cal1 ( n, mid1 ), cal2 ( n, mid1 ));
double len2 = max ( cal1 ( n, mid2 ), cal2 ( n, mid2 ));
if ( len1 < len2 )
{
ans = len1;
high = mid2;
}
else
{
ans = len2;
low = mid1;
}
}
printf("%.2lf\n",ans*ans);
}
return 0;
}

 

下面的迭代法转自http://hi.baidu.com/liugoodness/blog/item/1aaebb16494b314320a4e9ad.html

#include <iostream>
#include <cstdio>
#include <cmath>
#define MAX 1000000000
#define MIN -1000000000
#define PI (asin(1.)*2)
using namespace std;
long x[50],y[50];
int main()
{
long t, n, j, i;	
double stepLen, from, num, left, right, up, down;
double nx, ny, border, minBorder, minA, a, getSin, getCos;
scanf("%ld",&t);
while ( t-- )	
{
scanf("%ld",&n);
for ( j = 0; j < n; j++ )
scanf ("%ld%ld",&x[j], &y[j] );
from = 0; num = 15; minBorder = MAX; stepLen = PI / 18; a=0;
while ( num-- )
{
for ( i = 0; i < 10; i++ )
{
getSin = sin(a); getCos = cos(a);
down = left = MAX;
up = right = MIN;
for ( j = 0; j < n; j++ )
{
nx = x[j] * getCos - y[j] * getSin;
ny = y[j] * getCos + x[j] * getSin;
if ( nx < left ) left = nx;
if ( nx > right) right = nx;
if ( ny < down ) down = ny;
if ( ny > up ) up = ny;
}
border = right - left;
border = ( up - down ) > border ? ( up - down ) : border;
if ( border < minBorder ) minBorder = border, from = a;
a += stepLen;
}
a = from - stepLen;
stepLen /= 4.5;
}
printf("%.2lf\n",minBorder*minBorder);
}
return 0;
}

 

这篇关于POJ 3301 Texas Trip (三分求极限）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---