2015.2.25

0.求最大公约数函数 int gcd( int a, int b) { //求最大公约数 if (a b) return gcd(b, a); if (b % a == 0 ) return a; return gcd(b % a, a);} 1.关于qsort与sort 1.1.qsort，包含在stdlib.h中 void qsort( list , sizeof ( list ), sizeof (Element_type)

0.求最大公约数函数

<code><span>int</span> gcd(<span>int</span> a, <span>int</span> b) {     <span>//求最大公约数 </span>
    <span>if</span>(a > b) <span>return</span> gcd(b, a);
    <span>if</span>(b % a == <span>0</span>) <span>return</span> a;
    <span>return</span> gcd(b % a, a);
}</code>

1.关于qsort与sort

1.1.qsort，包含在stdlib.h中

<code><span>void</span> qsort(<span>list</span>, <span>sizeof</span>(<span>list</span>),<span>sizeof</span>(Element_type),Comp); <span>// qsort的4个参数：数组的首地址、数组的实际大小，元素的实际大小，比较函数</span>

<span>int</span> cmp(<span>const</span> <span>void</span> *p1,<span>const</span> <span>void</span> *p2 )<span>//一般比较函数</span>
{
     <span>return</span> *((Element_type *)p2) > *((Element_type *)p1) ? <span>1</span> : -<span>1</span>;<span>//当p1>p2,return -1→降序排列（从大到小）</span>
     <span>/*return *(Element_type *)p1 - *(Element_type *)p2;
     是相同的效果；*/</span>
}
<span>int</span> cmp(<span>const</span> <span>void</span> *p1,<span>const</span> <span>void</span> *p2)<span>//字符串比较函数</span>
{
<span>return</span> <span>strcmp</span>((<span>char</span> *)p2,(<span>char</span> *)p1);<span>//p1>p2,return -1;t同理，降序排列；</span>
}
<span>int</span> cmp(<span>const</span> <span>void</span> *p1,<span>const</span> <span>void</span> *p2)<span>//一级结构体比较函数</span>
{
<span>return</span> (*(Node *)p2)->data > (*（Node *）p1)->data ? <span>1</span> : -<span>1</span>;
}</code>

1.2.sort，包含在头文件algorithm中

<code><span>//基础升序排列</span>
<span>void</span> sort(<span>begin</span>,<span>end</span>)；<span>//如int a[n];可用sort(a,a+n);</span>
<span>//自定义比较函数</span>
<span>void</span> sort(<span>begin</span>,<span>end</span>,compare);
bool compare(Element_type a,Element_type b)
{
      <span>return</span> a<b>//升序排列，如果改为return a>b，则为降序
}</b></code>

2.pair类函数，包含在using namespace std;中

<code>    pairint, <span>int</span>> p1;
    p1.first = <span>1</span>;
    p1.second = <span>2</span>;<span>//生成一个坐标为(1,2)的点，省略结构体定义过程</span>

    <span><span>set</span>int</span>, <span>int</span>> > a;<span>//生成一个数组a,a元素由(int,int)的点构成,a其实是个结构体数组</span>

    pairstring, pairint, <span>double</span>> > p3;
    p3.first = <span>"Memeda"</span>;
    p3.second.first = <span>2333</span>;
    p3.second.second = <span>2.13</span>;<span>//this is also ok;</span>

    make_pair(a,b)<span>//将数据a与b建立坐标联系，a与b数据类型不限</span>
    pair<a_element_type>(a,b)<span>//两者意思相近,前者自动匹配a,b数据类型,后者手动分配数据类型</span>

</a_element_type></code>

3.set类函数，包含在头文件set中（施工中）
部分介绍：

c++ stl集合(Set)是一种包含已排序对象的关联容器。set/multiset会根据待定的排序准则，自动将元素排序。两者不同在于前者不允许元素重复，而后者允许。

1) 不能直接改变元素值，因为那样会打乱原本正确的顺序，要改变元素值必须先删除旧元素，再插入新元素

2) 不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取，而且从迭代器角度来看，元素值是常数//鉴于还没搞清楚什么是迭代器，且慢总结

3) 元素比较动作只能用于型别相同的容器(即元素和排序准则必须相同)

set的各成员函数列表如下（查阅用）:

c++ stl容器set成员函数:begin()–返回指向第一个元素的迭代器

c++ stl容器set成员函数:clear()–清除所有元素

c++ stl容器set成员函数:count()–返回某个值元素的个数

c++ stl容器set成员函数:empty()–如果集合为空，返回true

c++ stl容器set成员函数:end()–返回指向最后一个元素的迭代器

c++ stl容器set成员函数:equal_range()–返回集合中与给定值相等的上下限的两个迭代器

c++ stl容器set成员函数:erase()–删除集合中的元素

c++ stl容器set成员函数:find()–返回一个指向被查找到元素的迭代器

c++ stl容器set成员函数:get_allocator()–返回集合的分配器

c++ stl容器set成员函数:insert()–在集合中插入元素

c++ stl容器set成员函数:lower_bound()–返回指向大于（或等于）某值的第一个元素的迭代器

c++ stl容器set成员函数:key_comp()–返回一个用于元素间值比较的函数

c++ stl容器set成员函数:max_size()–返回集合能容纳的元素的最大限值

c++ stl容器set成员函数:rbegin()–返回指向集合中最后一个元素的反向迭代器

c++ stl容器set成员函数:rend()–返回指向集合中第一个元素的反向迭代器

c++ stl容器set成员函数:size()–集合中元素的数目

c++ stl容器set成员函数:swap()–交换两个集合变量

c++ stl容器set成员函数:upper_bound()–返回大于某个值元素的迭代器

c++ stl容器set成员函数:value_comp()–返回一个用于比较元素间的值的函数

运用举例（待施工）：

<code><span>int</span> main()<span>//头文件略</span>
{
    <span><span>set</span>int</span>> S;
    S.insert(<span>77</span>);
    S.insert(<span>67</span>);
    S.insert(<span>88</span>);
    S.insert(<span>88</span>);
    <span>for</span>(<span><span>set</span>int</span>> :: iterator it = S.begin(); it != S.end(); it++)
        <span>cout</span>" ";
    <span>cout</span>//输出结果:67 77 88

    <span>return</span> <span>0</span>;
}</code>

4.计算几何技巧初窥.
例：
CodeForces - 514B
Han Solo and Lazer Gun

Description
There are n Imperial stormtroopers on the field. The battle field is a plane with Cartesian coordinate system. Each stormtrooper is associated with his coordinates (x,?y) on this plane.

Han Solo has the newest duplex lazer gun to fight these stormtroopers. It is situated at the point (x0,?y0). In one shot it can can destroy all the stormtroopers, situated on some line that crosses point (x0,?y0).

Your task is to determine what minimum number of shots Han Solo needs to defeat all the stormtroopers.

The gun is the newest invention, it shoots very quickly and even after a very large number of shots the stormtroopers don’t have enough time to realize what’s happening and change their location.

Input
The first line contains three integers n, x0 и y0 (1?≤?n?≤?1000, ?-?104?≤?x0,?y0?≤?104) — the number of stormtroopers on the battle field and the coordinates of your gun.

Next n lines contain two integers each xi, yi (?-?104?≤?xi,?yi?≤?104) — the coordinates of the stormtroopers on the battlefield. It is guaranteed that no stormtrooper stands at the same point with the gun. Multiple stormtroopers can stand at the same point.

Output
Print a single integer — the minimum number of shots Han Solo needs to destroy all the stormtroopers.

Sample Input

Input
4 0 0
1 1
2 2
2 0
-1 -1
Output
2

Input
2 1 2
1 1
1 0
Output
1

题目意思：给出双头枪的位置（x0, y0），以及 n 个突击队成员的坐标。双头枪射击一次，可以把它对住的方向（是直线，不是射线，因为是双头嘛）所有的人射杀掉。问将所有突击队成员消灭的最少射击数是多少。
解：
这题我首先想到的是斜率比较，输出不同斜率个数来实现，但由于两点坐标求斜率易出现精度误差，用斜率来直接求难度稍大，且难以debug，故采用累计不同向量方向的个数的方法来做。

<code><span>#include<cstdio></cstdio></span>
<span>#include<cstring></cstring></span>
<span>#include<iostream></iostream></span>
<span>#include<algorithm></algorithm></span>
<span>#include<set></set></span>
<span>using</span> <span>namespace</span> <span>std</span>;
<span>int</span> gys(<span>int</span> a, <span>int</span> b){<span>//求最大公约数</span>
    <span>if</span>(a > b) <span>return</span> gys(b , a);
    <span>else</span> <span>if</span>(b % a == <span>0</span>) <span>return</span> a;
    <span>return</span> gys(b % a ,a);
}

<span>int</span> main(){
    <span>int</span> x,y,n;
    <span><span>set</span><pair>int</pair></span> ,<span>int</span>> >a;
    <span>while</span>(<span>scanf</span>(<span>"%d %d %d"</span>, &n, &x, &y) != EOF){
        <span>int</span> p,q;
        <span>for</span>( <span>int</span> i = <span>0</span> ; i scanf(<span>"%d %d"</span>, &p, &q);
<span>//          cin >> p >> q;</span>
            p -= x; q -= y;
            <span>if</span>(p == <span>0</span>) a.insert(make_pair(<span>0</span>,<span>1</span>));
            <span>else</span> <span>if</span>(q == <span>0</span>) a.insert(make_pair(<span>1</span>,<span>0</span>));<span>//剪去（1,0）与（0,1）方向向量，</span>
            <span>else</span>{
                <span>int</span> t = gys(<span>abs</span>(p) ,<span>abs</span>(q));
                p/= t;
                q/= t;
                <span>if</span>(p 0){
                    p = -p;
                    q = -q;
                }
                a.insert(make_pair(p ,q));<span>//两点向量（p,q）p与q均除以最大公约数t，得到方向向量（p/t,q/t）</span>
            }
        }
<span>//      cout 
        <span>printf</span>(<span>"%d\n"</span>, a.size());<span>//输出不同方向向量个数即最少射击次数</span>
    }
            <span>return</span> <span>0</span>;
}</span></code>