1．合理种植
(plant.pas/.c/.cpp)
【问题描述】
大COS在氯铯石料场干了半年，受尽了劳苦，终于决定辞职。他来到表弟小cos的寒树中学，找到方克顺校长，希望寻个活干。
于是他如愿以偿接到了一个任务……
美丽寒树中学种有许多寒树。方克顺希望校园无论从什么角度看都是满眼寒树，因此他不希望有三棵甚至更多寒树种在一条直线上。现在他把校园里n棵寒树的坐标都给了大COS，让他数出存在多少多树共线情况。（若一条直线上有三棵或以上的树，则算出现一个多树共线情况。）
【输入】
输入文件名为plant.in。
第1行一个正整数n，表示寒树棵数。
接下来n行，每行两个非负整数x、y，表示一颗寒树的坐标。没有两颗寒树在同一位置。
【输出】
输出文件名为plant.out。
输出一个整数，表示存在多少多树共线情况。
【输入输出样例】
|
plant.in |
plant.out |
|
6 0 0 1 1 2 2 3 3 0 1 1 0 |
1 |
【数据范围】
对于30%的数据，有n≤10；
对于50%的数据，有n≤100；
对于100%的数据，有n≤1,000，0≤x,y≤10,000。
解题报告
考试的时候花了整整一个小时在纠结这道题上，结果还是没做出来，可能是因为我考虑的太多，不知道怎么标记判重，它的斜率从+10000~-10000，也不好记，又怕超时，就放弃了。结果这道题就是用斜率解的..（啊，无语=-=）。老师给的标程还没有理解，先记在这里有一笔。
同学提出了一种更容易理解的方法。先求出两两之间的斜率，但是注意要用long long ki=(y1-y2)*100000000LL/(x1-x2) 记录斜率，这样可以避免小数和double 判重的情况，然后枚举每三个点，如果任意两点之间k 相等，则三点共线。特殊处理：x1=x2的情况，斜率此时不存在，所以把它直接赋值为k=1，对后面的也不影响。那么，问题就到了记录判重的身上了。
定义一个数组used[1005][1005],如果共线三点中used[i][j]=used[i][k]=used[j][k]=true; 也许你就要问了，你只记录了三个点，如果有第4、5、6...个点都共线，不就不能判断了吗？但是，这样想，我们每次都按顺序枚举，如先开始used[1][2]=used[2][3]=used[1][3]=true了，那第四个点一定有
used[1][2]=used[1][4]=used[2][4]=true,依次类推，因为它们具有传递性，所以，所有这条线上的点都会被标记。这样一来就好办了。
代码如下：
#include<iostream>
#include<cstdio>
using namespace std;
int n;
struct pp{
int x, y;
};
pp tree[];
bool used[][]={false};
long long ki[][],ans;
int main()
{
freopen("plant.in","r",stdin);
freopen("plant.out","w",stdout);
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%d%d",&tree[i].x,&tree[i].y);
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
if (i!=j)
{
if (tree[i].x!=tree[j].x) ki[i][j]=(tree[i].y-tree[j].y)*100000000LL/(tree[i].x-tree[j].x);
else ki[i][j]=;
}
for (int i=;i<=n-;i++)
for (int j=i+;j<=n-;j++)
for (int t=j+;t<=n;t++)
if (ki[i][j]==ki[j][t])//!!! ==
{
if (used[i][j]||used[i][t]||used[j][t])
used[i][j]=used[i][t]=used[j][t]=true;
else
{
ans++;
used[i][j]=used[i][t]=used[j][t]=true;
}
}
printf("%lld",ans);//long long "%lld"
return ;
}
注意细节