8
8
2016
0

BZOJ 2338:[HNOI2011]数矩形

Problem

---------------------------分割线-----------------------------

这道题嘛。。是@ZHZX COOL讲课之前钦定窝来讲QAQ
于是就 biubiubabahonghong了。。听说只要把点两两连在一起然后找到一样长的中点还一样的就能组成矩形辣。然后算下面积。

代码如下:

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>

using namespace std;

#define Dev 1e-9

typedef pair<double,double> pdd;
typedef pair<int,int> pii;
#define X first
#define Y second
bool operator == (const pii&x, const pii&y){return x.X==y.X && x.Y==y.Y;}

struct Point{int x,y;}P[1510];
struct node{long long x,y;pii C;long long Len;}E[2300000];
bool cmp(node xx,node yy){return xx.Len<yy.Len;}
int tot;

bool operator !=(const node&x, const node&y)
{
	if(x.Len!=y.Len)return true;
	if(x.C==y.C)return false;
	return true;
}
long long ans=0,tmp;

int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d%d",&P[i].x,&P[i].y);
	tot=0;
	for(int i=1;i<=n;++i)
		for(int j=i+1;j<=n;++j)
		{
			++tot;
			E[tot].x=P[i].x-P[j].x; E[tot].y=P[i].y-P[j].y;
			E[tot].C.X=P[i].x+P[j].x; E[tot].C.Y=P[i].y+P[j].y;
			E[tot].Len=1ll*(P[i].x-P[j].x)*(P[i].x-P[j].x)+1ll*(P[i].y-P[j].y)*(P[i].y-P[j].y);
		}
	sort(E+1,E+1+tot,cmp);
	int now=1;
	for(int i=2;i<=tot;++i)
	{
		if(E[i].Len!=E[i-1].Len)now=i;
		else 
			for(int j=now;j<i;++j)
				if(E[i].C==E[j].C)
				{
					tmp=(E[i].x*E[j].y)-(E[j].x*E[i].y);
					ans=max(ans,abs(tmp));
				}
	}
	printf("%lld\n",ans/2);
	return 0;
}

感觉神清气爽。。。

Category: 程序 | Tags: 计算几何 排序 bzoj | Read Count: 181

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com