bzoj2338[HNOI2011]数矩形 计算几何

2338: [HNOI2011]数矩形

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 1535  Solved: 693
[Submit][Status][Discuss]

Description

bzoj2338[HNOI2011]数矩形 计算几何

Input

 

Output

 

Sample Input

 

Sample Output

 

HINT

 

Source

Day2

我开始想着记每条线的斜率,然后排序来找平行线,但却不能保证构成矩形。
一种新奇的思路:记录对角线,两条对角线长度相等且中点相同时可以确定一个矩形
然后题目就变得简单起来。枚举每两点,存放它们构成的线段,排序。
每条线段向前扩展找可以形成对角线的线段,找到之后更新答案。
为了避免精度错误,一切都可以用整形来计算,即算距离时不开根,中点不除2

 #include<bits/stdc++.h>
#define N 1505
#define ll long long
using namespace std;
int n,cnt;ll ans;
struct P{
int x,y;
bool operator < (const P &b)const{return x==b.x?y<b.y:x<b.x;}
P operator - (const P &b)const{return (P){x-b.x,y-b.y};}
bool operator == (const P &b)const{return x==b.x&&y==b.y;}
}p[N];
struct line{
ll len;P a,b,mid;
bool operator < (const line &b)const{return len==b.len?mid<b.mid:len<b.len;}
}l[N*N/];
ll dis(P a,P b){return 1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y);}
ll crs(P a,P b){return 1ll*a.x*b.y-1ll*a.y*b.x;}
void update(int i,int j){
P a=l[i].a,c=l[j].a,d=l[j].b;
P x=d-a,y=c-a;
//if(!crs(y,l[i].mid))y=d-a;
ll tmp=abs(crs(x,y));if(tmp>ans)ans=tmp;
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++){
l[++cnt].len=dis(p[i],p[j]);
l[cnt].a=p[i];l[cnt].b=p[j];
l[cnt].mid=(P){p[i].x+p[j].x,p[i].y+p[j].y};
}
sort(l+,l++cnt);int j;
for(int i=;i<=cnt;i++){
j=i-;
while(l[j].len==l[i].len&&l[j].mid==l[i].mid)update(i,j--);
}
printf("%lld\n",ans);
return ;
}
上一篇:Android的TextView与Html相结合的用法


下一篇:每天4亿行SQLite订单大数据测试(源码)