2338: [HNOI2011]数矩形

Time Limit: 20 Sec  Memory Limit: 128 MB

Submit: 1535  Solved: 693

[][][]

Description

Input

 

Output

 

Sample Input

 

Sample Output

 

HINT

 

Source

我开始想着记每条线的斜率，然后排序来找平行线，但却不能保证构成矩形。

一种新奇的思路：记录对角线，两条对角线长度相等且中点相同时可以确定一个矩形

然后题目就变得简单起来。枚举每两点，存放它们构成的线段，排序。

每条线段向前扩展找可以形成对角线的线段，找到之后更新答案。

为了避免精度错误，一切都可以用整形来计算，即算距离时不开根，中点不除2

1 #include
      
        2 #define N 1505 3 #define ll long long 4 using namespace std; 5 int n,cnt;ll ans; 6 struct P{ 7     int x,y; 8     bool operator < (const P &b)const{
    return x==b.x?y
       
        
         ans)ans=tmp;23 }24 int main(){25     scanf("%d",&n);26     for(int i=1;i<=n;i++)27     scanf("%d%d",&p[i].x,&p[i].y);28     for(int i=1;i<=n;i++)29         for(int j=i+1;j<=n;j++){30             l[++cnt].len=dis(p[i],p[j]);31             l[cnt].a=p[i];l[cnt].b=p[j];32             l[cnt].mid=(P){p[i].x+p[j].x,p[i].y+p[j].y};33         }34     sort(l+1,l+1+cnt);int j;35     for(int i=1;i<=cnt;i++){36         j=i-1;37         while(l[j].len==l[i].len&&l[j].mid==l[i].mid)update(i,j--);38     }39     printf("%lld\n",ans);40     return 0;41 }