4
12
2016
0

[BZOJ2338] [HNOI2011]数矩形

暴力的计算几何

暴力求出每一条线段,暴力比较是否能构成矩形

注意要long long不要double否则会炸精度

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
 
const int N=1505;
typedef long long LL;
 
int n,cnt;
LL ans; 
 
struct Point{
LL x,y;
Point(){}
Point(LL xs,LL ys){x=xs;y=ys;}
friend bool operator==(Point A,Point B){return A.x==B.x & A.y==B.y;}
friend Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
friend Point operator-(Point A,Point B){return Point(A.x-B.x,A.y-B.y);}
friend LL operator*(Point A,Point B){return A.y*B.x-A.x*B.y;}
friend bool operator<(Point A,Point B){return A.x<B.x || (A.x==B.x && A.y<B.y);}
}poi[N];
 
LL Dist(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}
Point MidPoint(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
 
struct Line{
Point a,b,mid;
LL dis;
Line(){}
Line(Point A,Point B,Point MID,LL DIS){a=A;b=B;mid=MID;dis=DIS;}
friend bool operator<(Line A,Line B){
return A.dis<B.dis || (A.dis==B.dis && A.mid<B.mid) || (A.dis==B.dis && A.mid==B.mid && A.a<B.a);
}
}line[N*N];
 
LL Abs(LL x){return x>0?x:-x;}
 
int main(){
freopen("2338.in","r",stdin);
freopen("2338.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%lld %lld",&poi[i].x,&poi[i].y);
}
for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        line[++cnt]=Line(poi[i],poi[j],MidPoint(poi[i],poi[j]),Dist(poi[i],poi[j]));
    }
}
sort(line+1,line+cnt+1);
for(int i=2;i<=cnt;i++){
    int j=i-1;
    while(line[j].mid==line[i].mid && line[j].dis==line[i].dis){
        ans=max(ans,Abs((line[i].a-line[j].a)*(line[i].a-line[j].b)));
        j--;
    }
}
printf("%lld\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 432

登录 *


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