【题目描述】
在 N 条水平线与 M 条竖直线构成的网格中，放 K 枚石子，每个石子都只能放在网格的交叉点上。问在最优的摆放方式下，最多能找到多少四边平行于坐标轴的长方形，它的四个角上都恰好放着一枚石子。
【输入】
输入文件包含多组测试数据。
第一行，给出一个整数T，为数据组数。接下来依次给出每组测试数据。
每组数据为三个用空格隔开的整数 N，M，K。
3 3 3 8 4 5 13 7 14 86
【输出】
对于每组测试数据，输出一行"Case #X: Y"，其中X表示测试数据编号，Y表示最多能找到的符合条件的长方形数量。所有数据按读入顺序从1开始编号。
Case #1: 5 Case #2: 18 Case #3: 1398
【题解】
首先先考虑对于一个布满点的矩形(x行，Y列)，所有的矩形总数为 C(2,x)*C(2,y)。要使数量最多，则x和y要尽可能接近（有最大行和最大列的限制）。 题中所给的K可能不能刚好排成大矩形，可能有多余的几个点，这几个点的数量一定不会超过一行或一列的最大数量。 试想如果超过，则多出来完整的一行或一列可以和原来的大矩形构成更大的矩形，剩下的点就不能构成完整的一行或一列了。
多余多出来的点，以一排或一列的形式，靠在大矩形短的一边（要注意是否到达边界），设多余K个点，则多增加的矩形数为 C(2,K)*L （L为长边的点数）。
为了简单起见，可以规定行大于列（对调旋转下），枚举 X、Y的有效极大组合，找出最大的结果就行了。
AC代码：
1 #include <stdio.h> 2 #include <string.h> 3 #include <math.h> 4 int n,m,k; 5 void swap(int &a,int &b) 6 { 7 int t=a; 8 a=b; 9 b=t; 10 } 11 long long getc(long long j) 12 { 13 return j*(j-1)/2; 14 } 15 int main() 16 { 17 int T; 18 scanf("%d",&T); 19 int cas=0; 20 while (T--) 21 { 22 scanf("%d%d%d",&n,&m,&k); 23 if (n<m) swap(n,m); 24 int t=sqrt(k); 25 int b=t>m?m:t; 26 int a=k/b>n?n:k/b; 27 long long max=0; 28 for (;b>=2 && a<=n;--b,a=k/b) 29 { 30 long long sum=getc(a)*getc(b); 31 int p=k-a*b; 32 if (a<n) 33 { 34 sum=sum+getc(p)*a; 35 } 36 else 37 { 38 sum=sum+getc(p)*b; 39 } 40 max=max>sum?max:sum; 41 } 42 printf("Case #%d: %I64d\n",++cas,max); 43 } 44 45 return 0; 46 }