UVA 10173

bitch bitch bitch...

TLE,WA一大坨，我是在拿生命来JUDGE啊。。

不得不说，UVA上的数据根本不是随机的，而是有预谋的。

for(int i=2;i<n;i++){
　　while(stop>1&&cross(p[i],p[st[stop-1]],p[st[stop-2]])>=0) stop--; //这个我本来是cross(p[i],p[st[stop-1]],p[st[stop-2]])>0
　　st[stop++]=i;
}

因为没加上一个“=”号，就把边上所有共线的点都搞上了，之后，由于N太大，无可奈何的TLE、WA了。呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵吕森哥哥哥哥哥可可

算法如下：

计算全部四个多边形的端点，称之为 xminP， xmaxP， yminP， ymaxP。
通过四个点构造 P 的四条切线。他们确定了两个“卡壳”集合。
如果一条（或两条）线与一条边重合，那么计算由四条线决定的矩形的面积，并且保存为当前最小值。否则将当前最小值定义为无穷大。
顺时针旋转线直到其中一条和多边形的一条边重合。
计算新矩形的面积，并且和当前最小值比较。如果小于当前最小值则更新，并保存确定最小值的矩形信息。
重复步骤4和步骤5，直到线旋转过的角度大于90度。
输出外接矩形的最小面积。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define min(x,y) ((x)<(y)?(x):(y))

using namespace std;

struct point

{

    double x,y;

}p[1005];

int ans[1005],st[1005],stop,cnt,n;

int DB (double d){

	if (fabs(d)<1e-8)

		return 0;

	return d>0?1:-1;

}

double cross (point a,point b,point c){

	return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);

}

double dot(point a,point b,point c){

    return (a.x-c.x)*(b.x-c.x)+(a.y-c.y)*(b.y-c.y);

}

bool cmp(point A,point B){

	if(A.y<B.y) return true;

	else if(A.y==B.y){

		if(A.x<B.x)return true;

	}

	return false;

}

void forTU(){

	stop=cnt=0;

	st[stop++]=0; st[stop++]=1;

	for(int i=2;i<n;i++){

		while(stop>1&&cross(p[i],p[st[stop-1]],p[st[stop-2]])>=0) stop--;

		st[stop++]=i;

	}

	for(int i=0;i<stop;i++)

	ans[cnt++]=st[i];

	stop=0; st[stop++]=n-1; st[stop++]=n-2;

	for(int i=n-3;i>=0;i--){

		while(stop>1&&cross(p[i],p[st[stop-1]],p[st[stop-2]])>=0) stop--;

		st[stop++]=i;

	}

	for(int i=1;i<stop;i++){

		ans[cnt++]=st[i];

	}

}

double roating(){

	cnt--;

    if(n<3) return 0;

    int i,m=1,q=1,r;

    double anst=1e10,a,b,c;

    for(i=0;i<cnt;i++){

		while (DB(cross(p[ans[(i+1)]],p[ans[(m+1)]],p[ans[i]])-cross(p[ans[(i+1)]],p[ans[m]],p[ans[i]])) >0)

  		m=(m+1)%cnt;

        while (DB(dot(p[ans[(q+1)]],p[ans[(i+1)]],p[ans[i]])-dot(p[ans[q]],p[ans[(i+1)]],p[ans[i]])) >0)

        q=(q+1)%cnt;

        if (i==0)

		r=q;

        while(DB(dot(p[ans[(r+1)]],p[ans[(i+1)]],p[ans[i]])-dot(p[ans[r]],p[ans[(i+1)]],p[ans[i]])) <= 0)

        r=(r+1)%cnt;

        a=cross(p[ans[(i+1)]],p[ans[m]],p[ans[i]]);

        b=dot(p[ans[q]],p[ans[(i+1)]],p[ans[i]])-dot(p[ans[r]],p[ans[(i+1)]],p[ans[i]]);

        c=dot(p[ans[(i+1)]],p[ans[(i+1)]],p[ans[i]]);

        anst=min(anst,a*b/c);

    }

    return anst;

}

int main (){

    while (scanf("%d",&n) && n!=0) {

        for (int i=0;i<n;i++)

		scanf("%lf%lf",&p[i].x,&p[i].y);

		sort(p,p+n,cmp);

        forTU();

        printf("%.4lf\n",roating());

    }

    return 0;

}

巴特西

UVA 10173

最新文章

热门文章