noj 1098 旋转卡壳.txt

ACM资料大集合

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
using namespace std;

//NOJ 1098 旋转卡壳
#define MAX 99999999
#define MIN -99999999
#define NMAX 35
#define PI 3.1415926
double fenshu[12]={100,10,10,10,10,10,10,10,10,10,10,10};

typedef struct point
{
	double x;
	double y;
}point;

point tubao[NMAX];//围成凸包的点,顺时针顺序
point shuru[NMAX];
point chuli[NMAX];
bool cmpx(point a,point b) {return a.x<b.x;}

bool dtb(point o,point a,int num)
{//判断点是否在oa向量的一侧，是则返回true,否则返回false;
	int i;
	for(i=1;i<=num;i++)
	{
		if(o.x*a.y+a.x*chuli[i].y+chuli[i].x*o.y
			-chuli[i].x*a.y-a.x*o.y-o.x*chuli[i].y>0) break; 
	}
	if(i==num+1) return true;
	else return false;
}

double get_gen2dis(point a,point b)
{
	return (pow(a.x-b.x,2)+pow(a.y-b.y,2))/2.0;
}

void print_tubao(int tbnum)
{
	int i;
	for(i=1;i<=tbnum;i++)
		cout<<tubao[i].x<<" "<<tubao[i].y<<endl;
	
}

/*
int create_tubao(int num)
{	//顺带得到凸包点的个数
	//求凸包的O(n^3)的算法
	int i,j;
	int flag[NMAX];
	point last;
	for(i=1;i<=num;i++) 
	{
		chuli[i]=shuru[i];
		flag[i]=0;
	}
	sort(chuli+1,chuli+1+num,cmpx);

	tubao[1]=chuli[1];
	last=chuli[1];
	flag[1]=1;
	j=1;
	while(true)
	{
		for(i=2;i<=num;i++)
		{
			if(flag[i]==0)
			{//已放入tubao[]里的点不访问
				if(dtb(last,chuli[i],num)==true)
				{	//符合dbt()的点都扔到tubao[]里
					tubao[++j]=chuli[i];
					last=chuli[i];
					flag[i]=1;
					break;
				}
			}
		}
		if(i==num+1) break;//找到了所有凸包点
	}
	return j;
}
*/
double get_dis(point a,point b)
{	//求两点距离
	return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}

double get_dj(point oa,point a,point ob,point b)
{	//求得向量oa->a,ob->b的点积
	return (a.x-oa.x)*(b.x-ob.x)+(a.y-oa.y)*(b.y-ob.y);
}

double get_mianji(point a,point b,point c)
{
	return a.x+b.y+c.x*a.y+b.x*c.y-c.x*b.y-b.x*a.y-a.x*c.y;
}
double get_high(point o,point a,int tbnum)
{	//通过离向量o->a距离最远的点，求得高
	int i;
	double s,high,max=MIN,min=MAX;
	for(i=1;i<=tbnum;i++)
	{
		s=get_mianji(o,a,tubao[i]);
		if(max<s) max=s;
		if(min>s) min=s;
	}
	high=(max-min)/get_dis(o,a);
	return high;
}

double get_wide(point o,point a,int tbnum)
{	//通过与向量o->a距离点积最大最小的点，求得宽
	int i;
	double min,max,temp,tt,result;
	min=MAX;max=MIN;
	point mindian,maxdian;
	for(i=1;i<=tbnum;i++)
	{
		temp=get_dj(o,a,o,tubao[i]);
		if(min>temp) {min=temp;mindian=tubao[i];}
		if(max<temp) {max=temp;maxdian=tubao[i];}
	}
	temp=(double)fabs(get_dj(o,a,mindian,maxdian));
	tt=get_dis(o,a);
	result=temp/tt;
	return result;
}

point rotate(point o,double alpha,point p) 
{ //点p绕点o旋转alpha角后的坐标
	point tp; 
	p.x-=o.x; 
	p.y-=o.y; 
	tp.x=p.x*cos(alpha)-p.y*sin(alpha)+o.x; 
	tp.y=p.y*cos(alpha)+p.x*sin(alpha)+o.y; 
	return tp; 
} 

/*
double get_angle(point o,point s,point e) 
{	//返回顶角在o点，起始边为os，终止边为oe的夹角
	double cosfi,fi,norm; 
	double dsx = s.x - o.x; 
	double dsy = s.y - o.y; 
	double dex = e.x - o.x; 
	double dey = e.y - o.y; 

	cosfi=dsx*dex+dsy*dey; 
	if(((double)(fabs(cosfi)))<0.00001) cosfi=0;
	norm=(dsx*dsx+dey*dey)*(dex*dex+dey*dey); 
	cosfi /= sqrt( norm ); 

	if (cosfi >= 1.0 ) return 0; 
	if (cosfi <= -1.0 ) return -3.1415926; 

	fi=acos(cosfi); 
	if (dsx*dey-dsy*dex>0) return fi; // 说明矢量os 在矢量 oe的顺时针方向 
	return -fi; 
} 
*/
double xzkk(int tbnum)
{//用旋转卡壳法求解最大覆盖正方形的面积，xzkk=旋转卡壳，那xzdsm=???
 //枚举所有度数求，先枚举一个大致角度，然后在最优角度附近逐次逼近
   int i,j,k;
   double wide,high,bc,min,answer;
   double alpha,pal,end,begin,minalp;
   double zumin[NMAX],lastbc,longbc;

   point last,now,temp,p1,p2,tt;
   p1.x=0.00;p1.y=0.00;p2.x=1.00;p2.y=0.00;
   min=MAX;
   //初始的角度范围是0~PI/2 
	begin=0;
	end=PI/2;
	//fenshu[]一开始很大，后来很小，因为确定第一次的大致角度很重要
   pal=(end-begin)/fenshu[0];
	for(i=1;i<=11;i++)
	{
		for(alpha=begin,j=1;alpha<=end;alpha+=pal,j++)
		{
			temp=rotate(p1,alpha,p2);
			wide=get_wide(temp,p1,tbnum);
			high=get_high(temp,p1,tbnum);
			if(wide>high) bc=wide;
			else bc=high;
			if(bc<min) {min=bc;minalp=alpha;}
		}
		//minalp是这一次的最优角度
		begin=minalp-pal; 
		end=minalp+pal;
		//在最优角度附近逐次逼近，下一次的范围就是minalp-pal ~ minalp+pal
		pal=(double)fabs((end-begin)/fenshu[i]);
		if(pal<0.0000000000000001) break;
	}
	answer=pow(min,2);
  return answer;
}

typedef struct vec
{
	double x;
	double y;
	double len;
}vec;

double get_dj(vec a,vec b)
{//向量a,b的点积
	return a.x*b.x+a.y*b.y;
}

double get_qj(vec a)
{
	if(a.x==0&&a.y>0) return PI/2;
	else if(a.x==0 && a.y<0) return 3*PI/2;
	else if(a.x<0) return atan(a.y/a.x)+PI;
	else if(a.x>0&&a.y<0) return atan(a.y/a.x)+2*PI;
	else return atan(a.y/a.x);
}
bool cmqj(point a,point b)
{//比较a,b关于水平线的倾角
	point o;
	vec oa,ob;
	//点o是多边形任意三个点所围成三角形的重心，这个点必在凸包内
	o.x=(shuru[1].x+shuru[2].x+shuru[3].x)/3;
	o.y=(shuru[1].y+shuru[2].y+shuru[3].y)/3;
	//o->s是水平方向长度为1的向量
	oa.x=a.x-o.x; oa.y=a.y-o.y; oa.len=sqrt(pow(a.x-o.x,2)+pow(a.y-o.y,2)); 
	ob.x=b.x-o.x; ob.y=b.y-o.y; ob.len=sqrt(pow(b.x-o.x,2)+pow(b.y-o.y,2)); 
	return get_qj(oa)<get_qj(ob);
}

bool cmfx(point mm,point o,point e)
{//判断点mm是不是在向量p->e的左侧
	double a,b,c;
	a=e.y-o.y;b=o.x-e.x;c=o.x*e.y-o.y*e.x;
	if(mm.x*a+b*mm.y<c) return true;
	return false;
}

int get_next(int now,int num)
{
	if(now==num) return 1;
	else return now+1;
}

int create_xulie(int num)
{
	int i,j;
	point temp[NMAX];
	for(i=1;i<=num;i++) temp[i]=shuru[i];
	sort(temp+1,temp+1+num,cmqj);
	chuli[1]=temp[1];
	j=1;
	for(i=2;i<=num;i++)
	{
		if(!(temp[i].x==temp[i-1].x &&temp[i].y==temp[i-1].y)) chuli[++j]=temp[i];
	}
	return j;
}

int create_tubao(int num)
{
	//scan算法求凸包，O(nlogn)
	int minnum,rnum;
	int i,s;
	double min;
	min=MAX;
	rnum=create_xulie(num);
	for(i=1;i<=rnum;i++) if(chuli[i].x<min) {min=chuli[i].x;minnum=i;}
	tubao[1]=chuli[minnum];
	i=get_next(minnum,rnum);
	tubao[2]=chuli[i];
	s=2;//栈顶位置
	i=get_next(i,rnum);
	do
	{
		//注意s>=2，这样栈最多退到只剩一个点 
		while(cmfx(chuli[i],tubao[s-1],tubao[s])==false&&s>=2)
			s--;
		tubao[++s]=chuli[i];//满足凸包条件，或栈只剩一个点时
		i=get_next(i,rnum);
	}
	while(!((chuli[i].x==tubao[1].x)&&(chuli[i].y==tubao[1].y)));//循环一圈
	//最后一个点是否在凸包上，还要再判断
	if(cmfx(chuli[i],tubao[s-1],tubao[s])==false) s--;
	return s;
}
/*
int main()
{
	int num,i,j,casenum,tbnum,bb;
	FILE *fp;
	double ans;
	scanf("%d",&casenum);
	fp=fopen("my_out.txt","w");
	for(i=1;i<=casenum;i++)
	{
		scanf("%d%d",&bb,&num);
		for(j=1;j<=num;j++)
			cin>>shuru[j].x>>shuru[j].y;
		tbnum=create_tubao(num);//构造凸包
		if(tbnum>=3)
		{
			ans=xzkk(tbnum);
			fprintf(fp,"%d  %.2f\n",i,ans);
		}
		else if(tbnum==2)
			fprintf(fp,"%d  %.2f\n",i,get_gen2dis(tubao[1],tubao[2]));
		else fprintf(fp,"%d  0.00\n",i);
	}
	fclose(fp);
	return 0;
}
*/

int main()
{
	int num,i,j,casenum,tbnum,bb;
	scanf("%d",&casenum);
	for(i=1;i<=casenum;i++)
	{
		scanf("%d",&num);
		for(j=1;j<=num;j++)
			cin>>shuru[j].x>>shuru[j].y;
		tbnum=create_tubao(num);//构造凸包
		if(tbnum>=3)
			printf("%.2f\n",xzkk(tbnum));
		else if(tbnum==2)
			printf("%.2f\n",get_gen2dis(tubao[1],tubao[2]));
		else printf("0.00\n");
	}
	return 0;
}