8
8
2016
2

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: 950
Avatar_small
Cyber Security Inter 说:
2022年8月08日 19:38

One thing you should understand is that there is no precise and standalone site where you will be able to find only Cyber Security Internships right away. But we have found some of the best sites online that you will be able to browse to find out the best Internship option for the Cyber Security role. Cyber Security Internships Cyber Security is a broader term coined into to understand the main role of security maintenance of the IT companies when it comes to the Cyber unit, which is the cloud connection.

Avatar_small
Rajasthan Board Ques 说:
2022年10月04日 01:29

Rajasthan Board Model Paper 2023 Pdf Download for School Education Ajmer & Jaipur Board Sample Model Question Paper for Class 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 & 12 Standard Theory, Objective (MCQ) and Bit Questions for Hindi Medium, English Medium, Urdu Medium and others. New Exam Scheme orRajasthan Board Question Paper Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.


登录 *


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