海伦公式由于要多次开平方，会导致积累误差，所以通常用矢量叉乘来计算，其原理在绝大多数空间解析几何的书中都可以找到，此处不赘述。

程序如下：

 

#define SQR(x) ((x) * (x))

 

//二维的情况，假设三个顶点坐标分别为(x[i], y[i]), (x[j], y[j]), (x[k], y[k])

double areaTri_2dimension(int i, int j, int k)

{

 double x1 = x[j] - x[i];

 double y1 = y[j] - y[i];

 double x2 = x[k] - x[i];

 double y2 = y[k] - y[i];

 return 0.5 * fabs(x1 * y2 - y1 * x2);

}

 

From SRM 288

低级错误：

1. 写错循环变量。

2. 定义vector<int> c; 还没push_back数据就试图用[]进行访问。

3. memset(a, 1, sizeof(a))，如果a的元素是int类型，这样写无法将a的每个元素赋1，原因是大多数编译器的int占4个字节，这个语句实际上是将a所在的内存空间中的每个字节都赋值1，注意是每个字节而不是每个数组元素！所以这样做的结果是将每个元素都赋二进制值1000000010000000100000001，相当于十进制的16843009。

中级错误：

1. 数组访问越界。

避免方法：一定要小心[]中的表达式！

2. for (i=0; i<a.size()-1; i++)导致程序运行超时，因为size()返回的数值是unsigned int，所以计算  a.size()-1时，会将结果也转化为unsigned int，负数会变成正数！

避免方法：将a.size()的结果强制转化为int，写成宏#define SIZE(A) (int((A).size()))

高级错误：

已知三角形三点坐标求面积时如果用海伦公式，会由于多次计算平方根而导致积累误差，所以应该用向量的叉乘来计算面积。

TopCoder的SRM 284在北京时间的1月22日凌晨一点举行。10点多进入比赛房间时，已经有将近100号人，其中最著名的人物应该就是排名第4的斯洛伐克人misof。等到晚上11点多，排名第1的俄罗斯人petr也来了，此时，偶决定去做一件伟大无比的事－－洗冷水澡！其实不是偶有自虐倾向，实在是因为没热水啊。。。临近1点，房间分好，偶分在Room 3，高手云集，有misof，瑞典第一高手Yarin，日本选手中排名第一的natori，还有印度800多名选手中排名第2的konqueror，还有两位来自浙大的同胞。比赛准时开始，250分的题目是一道组合题，给定三角形边长的范围，求符合条件的三角形数目，二十多分钟做完。500分的题目是关于文字压缩的，因为算法都给出了，所以是一道模拟题。觉得繁，便又打开800分的题目，关于康托集的题目，似乎要做高精度除法，同样繁。。。两繁相权取其简，于是决定做500分的题，做的过程很担心做不完，比赛结束还有9分钟的时候编译通过，test了三个example，似乎没什么问题，提交。回到房间，发现misof等人已经砍完所有题目在聊天室里聊天了，太牛了！剩下几分钟也做不了800分的题目了，只好一边检查500分的题一边等待Coding Phase的结束。Coding Phase结束，Challenge Phase开始，终于见识到了大牛们找bug的能力，仅过了几分钟，好多人的程序就纷纷被拿下，偶500分的题目也难幸免。。。而斯洛伐克人、印度人、日本人和瑞典人一直稳居前4。一个多小时的System Test结束，最终斯洛伐克人排名整个Divsion的第一，这也使他一举跃升到世界排名第一的位置，取代了占据这一位置数月的petr。偶最终排Divsion的第169位，还算中间位置，由于刚进入这一Division，所以还是获得了将近100分的积分，哈，又要窃喜了。

SRM 283，被分到了Room 36，300分的题目很简单，房间里大多数人都在几分钟内搞掂，600分的题目是一道计算几何题，求与平面上尽可能多的点接近的直线，需要排序，用pair类实现比较简单，前几天在Blog上写的STL用法笔记有了用武之地，呵，看来以后要多写Blog。由于对pair的用法还不熟练，竟然不知道怎么获得pair的第一个元素（汗。。。），摸索了一下才找到方法。半个多小时才提交了题目。1000分的题目是道数论题，求a的阶乘和b的最大公约数，不难，十多分钟写完，提交。比赛还剩20多分钟，对600分的题目不放心，继续check，觉得有个地方错了，改，交；又发觉没错（分特！），再改回，再交，由于重复提交被扣了100多分：（（（。比赛还剩10来分钟，发现Room里面有人用汉语找我聊天，哈，看来参加TopCoder的中国人还不少。看了一下Summary，只有偶和这位中国同胞完成了3题，他用的时间比我少，所以我暂时排第二。Coding Phase结束，还是我们两个人依然排在前两位。很快，激动人心的Challenge Phase开始，每个人开始为自己对手的程序挑bug。很不幸，我们两个人1000分的题目都被找到bug，于是排名都降到了第4和第5位。Chanllenge结束后，郁闷地等待System Test。一个多小时后（现在参加TopCoder的人越来越多，System Test的时间也越来越长。。。），System Test结束，惊喜地发现自己成了房间的NO.1，原来排在前面的几位1000分的题目都在System Test中fail掉了，那位中国同胞的600分题也没过。查了总排名，自己排到31位，总共有20几个房间，看来运气真的不错，换了房间很可能就拿不到第一了，窃喜之。系统发消息过来，说每个房间的第一名有39 dollars的奖金，才想起这次比赛是有奖金的，再窃喜之。不过到现在还不知道这么少的奖金，米国那边会怎么把发过来，估计收到可能性不大，哈，不过这次比赛后，涨了100多分，升了一级，下次比赛可以和牛人们在一个Division，会碰到谁呢？已经占据排行榜第一把交椅多时的天才少年petr？被誉为世界算法武功第一，但久未露面的SnapDragon？还是清华的领军人物，只用了5次比赛便跻身世界前100名的fuwenjie？期待ing...

C++的标准模板库（Standard Template Library，简称STL）是一个容器和算法的类库。容器往往包含同一类型的数据。STL中比较常用的容器是vector，set和map，比较常用的算法有Sort等。

 

一. vector

一个vector类似于一个动态的一维数组。

vector<int> a; //声明一个元素为int类型的vector a

vectot<MyType> a; //声明一个元素为MyType类型的vector a

这里的声明的a包含0个元素，既a.size()的值为0，但它是动态的，其大小会随着数据的插入和删除而改变。

而

vector<int> a(100, 0); //这里声明的是一已经个存放了100个0的整数vector

我们可以通过[]操作符或函数at来访问vector中的元素，例如

cout<<a[5]<<endl;

cout<<a.at(5)<<endl;

两者的区别在于后者在访问越界时会抛出异常，而前者不会。

另一个很常用的函数是push_back，用于在vector的末尾添加元素，如

a.push_back(5);

其它常用函数

size_t size();       // 返回vector的大小，即包含的元素个数
void pop_back();     // 删除vector末尾的元素，vector大小相应减一
T back();            // 返回vector末尾的元素

void clear();        // 将vector清空，vector大小变为0

二. Sort

Sort顾名思义就是排序。

Sort的用法非常简单，对于vector a来说

Sort(&a[0], &a[N]); //N=a.size()

将a中元素递增排序。

对于我们自己定义的类或结构，可以定义相应的运算符<

bool operator<(const MyType &x, const MyType &y)
{
  // Return true if x<y, false if x>=y
}
对于多关键字的排序，我们也可以利用类pair。

一个pair包含两个元素，排序时先按第一个元素从小到大排，对于第一个元素相等的pair，再按第二个元素从小到大排，例如

int N,x,y;
vector< pair<int,int> > a; // 注意这里两个> >中间必须有一个空格，否则编译器会当是运算符>>
cin >> N;
for(int i=0;i<N;++i) {
  cin >> x >> y;
  a.push_back(make_pair(x,y)); // make_pair用于创建pair对象
}
sort(&a[0], &a[N]);

 

三. set

set是集合，set中不会包含重复的元素，这是和vector的区别。

定义一个元素为整数的集合a，可以用

set<int> a;

对集合a中元素的基本操作有

插入元素：a.insert(1);

删除元素（如果存在）：a.erase(1);

判断元素是否属于集合：if (a.find(1) != a.end()) ...

返回集合元素的个数：a.size()

将集合清为空集：a.clear()

集合的并，交和差

set_union(a.begin(),a.end(),b.begin(),b.end(),insert_iterator<set<int> >(c,c.begin()));
set_intersection(a.begin(),a.end(),b.begin(),b.end(),insert_iterator<set<int> >(c,c.begin()));
set_difference(a.begin(),a.end(),b.begin(),b.end(),insert_iterator<set<int> >(c,c.begin()));

注意在此前要将c清为空集。

很重要的一点，为了实现集合的快速运算，set的实现采用了平衡二叉树，因此，set中的元素必须是可排序的。如果是自定义的类型，那在定义类型的同时必须给出运算符<的定义（定义方式见上文）。