题目大意：找小于N的互素数个数。
解决方法1：对从1~N的每个数求它与N的最大公约数，如果等于1读数器加1，最后输出结果。
解决方法2：对从1~N的数组遍历，如果这个数没有被处理过(一定是质数)，则判断它是否能被N整除，如果可以，则这个质数的所有倍数都一定不与N互素；如果不可以，则这个质数一定不与N互素，而它的倍数可能与N互素。处理一遍后，计算可能互素及一定互素的数的个数。
下面只贴方法2的代码：

#include <iostream>
using namespace std;

int num[10001];
int main() {
    int i, j, N, cnt = 0;
    memset(num,-1,sizeof(num));
    num[0] = 1, num[1] = 3;
    cin >> N;
    for(i = 2; i <= N; i++) {
        if(num[i] != -1)    continue;
        if(N%i == 0) {
            // must not
            for(j = i; j <= N; j += i)
                num[j] = 1;
        }
        else {
            // must be
            num[i] = 3;
            for(j = i+i; j <= N; j += i)
                num[j] &= 7;
        }
    }
    for(i = 1; i <= N; i++) {
        if((num[i] & 3) == 3)    cnt++;
    }
    cout << cnt << endl;
    return 0;
}

      这题wa到无语，实在找不出来是什么原因，我是把两个例子的图在坐标纸上画出来，发现很像是垂心，上网看，的确这样，可是找不到证明，我自己也尝试了下，没什么思路，如果有大牛会证，写个思路哈~
      还有就是我这代码，是推公式的，根据垂心与一个顶点组成的向量与另外两点组成的向量内积为0推出来的，自己随机生成的数据都过了，可是不知道怎么回事，Discuss中说可能和编译器有关，我还是wa，嗨，还望高人指点啊~~

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define Type double
struct Point{
    Type x, y;
};
void Orthocenter( Point p1, Point p2, Point p3, Point &p ){
    Point v1, v2;
    v1.x= p1.x- p2.x, v1.y= p1.y- p2.y;
    v2.x= p2.x- p3.x, v2.y= p2.y- p3.y;
    p.y= (v2.x*p1.x+v2.y*p1.y-(v1.x*p3.x+v1.y*p3.y)*v2.x/v1.x)/(v2.y-v2.x*v1.y/v1.x);
    p.x= p3.x+v1.y*(p3.y-p.y)/v1.x;
}
int main(){
    int n;
    Point p1, p2, p3, p;
    scanf("%d",&n);
    while( n-- ){
        scanf("%lf%lf%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y,&p3.x,&p3.y);
        Orthocenter(p1,p2,p3,p);
        printf("%.4lf %.4lf\n",p.x,p.y);
    }
    return 0;
}

PS.顺手copy了点性质，可是wa到没心情再去证明了……
1:垂心
三角形三边上的高的交点称为三角形的垂心。三角形垂心有下列有趣的性质：设△ABC的三条高为AD、BE、CF，其中D、E、F为垂足,垂心为H。
性质1 垂心H关于三边的对称点，均在△ABC的外接圆上。
性质2 △ABC中,有六组四点共圆，有三组(每组四个)相似的直角三角形，且AH·HD=BH·HE=CH·HF。
性质3 H、A、B、C四点中任一点是其余三点为顶点的三角形的垂心(并称这样的四点为一垂心组)。
性质4 △ABC,△ABH,△BCH,△ACH的外接圆是等圆。
性质5 在非直角三角形中,过H的直线交AB、AC所在直线分别于P、Q，则 AB/AP·tanB+ AC/AQ·tanC=tanA+tanB+tanC。
性质6 三角形任一顶点到垂心的距离，等于外心到对边的距离的2倍。
性质7 设O，H分别为△ABC的外心和垂心，则∠BAO=∠HAC，∠ABH=∠OBC，∠BCO=∠HCA。
性质8 锐角三角形的垂心到三顶点的距离之和等于其内切圆与外接圆半径之和的2倍。
性质9 锐角三角形的垂心是垂足三角形的内心；锐角三角形的内接三角形(顶点在原三角形的边上)中，以垂足三角形的周长最短。
2:内心
三角形的内切圆的圆心简称为三角形的内心，内心有下列优美的性质：
性质1 设I为△ABC的内心,则I为其内心的充要条件是：到△ABC三边的距离相等。
性质2 设I为△ABC的内心，则∠BIC=90°+12∠A，类似地还有两式；反之亦然。
性质3 设I为△ABC内一点，AI所在直线交△ABC的外接圆于D。I为△ABC内心的充要条件是ID=DB=DC。
性质4 设I为△ABC的内心，BC=a，AC=b，AB=c，I在BC、AC、AB上的射影分别为D、E、F；内切圆半径为r，令p= (1/2)(a+b+c)，则(1)S△ABC=pr；(2)r=2S△ABC/a+b+c ；(3)AE=AF=p-a,BD=BF=p-b,CE=CD=p-c；(4)abcr=p·AI·BI·CI。
性质5 三角形一内角平分线与其外接圆的交点到另两顶点的距离与到内心的距离相等；反之，若I为△ABC的∠A平分线AD(D在△ABC的外接圆上)上的点，且DI=DB，则I为△ABC的内心。
性质6 设I为△ABC的内心，BC=a，AC=b，AB=c，∠A的平分线交BC于K,交△ABC的外接圆于D，则 AI/KI =AD/DI =DI/DK = (b+c)/a。
3:外心
三角形的外接圆的圆心简称三角形的外心.外心有如下一系列优美性质：
性质1 三角形的外心是三角形三条边垂直平分线的交点；三角形的外心到三顶点的距离相等，反之亦然。
性质2 设O为△ABC的外心，则∠BOC=2∠A，或∠BOC=360°-2∠A(还有两式)。
性质3 设三角形的三条边长，外接圆的半径、面积分别为a、b、c,R、S△，则R=abc/4S△。
性质4 过△ABC的外心O任作一直线与边AB、AC(或延长线)分别相交于P、Q两点，则AB/AP ·sin2B+ AC/AQ·sin2C=sin2A+sin2B+sin2C。
性质5 锐角三角形的外心到三边的距离之和等于其内切圆与外接圆半径之和。
4:重心
性质1 设G为△ABC的重心，△ABC内的点Q在边BC、CA、AB边上的射影分别为D、E、F，则当Q与G重合时QD·QE·QF最大；反之亦然。
性质2 设G为△ABC的重心，AG、BG、CG的延长线交△ABC的三边于D、E、F,则S△AGF=S△BGD=S△CGE；反之亦然。
性质3 设G为△ABC的重心，则S△ABG=S△BCG=S△ACG= (1/3)S△ABC；反之亦然。       这题让我回忆起一些高中的空间几何了，嗨，都忘的不成样子了……
      对于任意经度和纬度的两点A和B，求球面距离，我的做法是先求AB的直线距离，再求AB对球心的夹角，从而得到球面距离。求AB是先求A和B到对应纬度平面的圆心Oa和Ob的距离以及Oa和Ob的距离，再由AB的经度求出直线AOa和BOb的夹角，再由异面直线上两点的距离公式求得，如果不记得上网找找，或者回去翻翻高中课本~~
      有一点很需要注意，同样是精度问题，不过它设计的很巧妙，我也是看Discuss才想到的，就是最后的Danger输出与否必须和你实际输出的数字相一致，比如99.995，你就应该输出100，而且它不要输出Danger，因此实际比较的时候不是和100比，而是和99.995比~~

      黑书上计算几何第二个例题，到现在才做到。
      思路黑书上已经讲的很清楚了，我讲下实现的细节。一开始我是打算用把当前考虑的线段延长的方法来做的，可是发现可能它不与任何线段相交，但它也不在管道内，这个很容易理解，因此换个思路，对于每个线段，对每个横坐标，判断它的延长线在该处的y值是不是在管道内，如果是，则考虑下一个X，否则计算交点，由于计算交点的时候只要考虑这条线段右边端点的右边情况就可以了，因为如果在右端点之前相交，光线根本到达不了那。而且如果计算出来的y比第k段上面的y大，说明交点是在k-1~k段的上管道，否则在k-1~k的下管道。
      要特别注意的两点，一个是初始化最远点坐标时，不能习惯性的初始化为0，我为此wa了一次，另外精度很重要，在判断是否在管道内的时候，要用eps，而且eps要设的足够小，我没设wa了一次，设为1e-6又wa了一次……设为1e-8才能过~~       解析几何的知识，已知不共线的三点求外接圆方程。
      这题很简单，不要想繁，我测试过，没有任何要输出的数据为0，就算有，直接输出0就好，不用省略。
      圆的方程先求圆心坐标，圆心坐标在两边中垂线的交点上，由此可以列出两个方程，求解得到坐标，注意分母为0的情况就好了，接着求半径就不用说了~~

      这道题灵活的考察了凸包的性质，是Graham算法的变形，要求的是永不右转的最长路径，其实题目中最大的数量一定是n，这很容易想到，相当于一圈圈的剥洋葱一样，每次取最外面的点，总能取遍所有的点。
      我的算法也是这样设计的，每一次都是找凸包，找完当前的凸包以后，以最后一个点为始点，重新按极角排序后再找，直到所有的点都被找遍为止。
      这题比较麻烦，模板改动也比较多，要理解几个函数的含义才能做得出来，下面是我的实现代码：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define eps 1e-8
struct Point{int x,y,k;};
Point pt[61], stk[61];
int Xmult(Point p1,Point p2,Point p0){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
Point p1,p2;
int graham_cp(const void* a,const void* b){
    int ret=Xmult(*((Point*)a),*((Point*)b),p1);
    return (ret==0)?(Xmult(*((Point*)a),*((Point*)b),p2)>0?-1:1):(ret>0?-1:1);
}
void ASort( int n, Point* pt ){
    int i,k=0;
    for (p1=p2=pt[0],i=1;i<n;p2.x+=pt[i].x,p2.y+=pt[i].y,i++)
        if (p1.y-pt[i].y>eps||((p1.y-pt[i].y==0)&&p1.x>pt[i].x))
            p1=pt[k=i];
    p2.x/=n,p2.y/=n;
    pt[k]=pt[0],pt[0]=p1;
    qsort(pt+1,n-1,sizeof(Point),graham_cp);
}
int main(){
    int t, n, m, i, j, cnt;
    scanf("%d",&t);
    while( t-- ){
        scanf("%d",&n);
        for( i= 0; i< n; i++ )    scanf("%d%d%d",&pt[i].k,&pt[i].x,&pt[i].y);
        cnt= 0,    m= n;
        ASort(m,pt);
        while( cnt< n ){
            for( stk[cnt++]=pt[0],stk[cnt++]=pt[1],stk[cnt++]=pt[2],i=3,j=1; i< m; i++ ){
                for( ;cnt>2&&Xmult(stk[cnt-2],pt[i],stk[cnt-1])>=0; pt[j++]=stk[--cnt] );
                stk[cnt++]=pt[i];
            }
            pt[0]= stk[--cnt], m= j;
            qsort(pt+1,m-1,sizeof(Point),graham_cp);
        }
        printf("%d",n);
        for( i= 0; i< n; i++ )
            printf(" %d",stk[i].k);
        putchar('\n');
    }
    return 0;
}

      这两题几乎是一样的，都是求给定半径的圆能覆盖的最多点的个数。我想的方法是O(n^3)的，时间用的比较多……
      思路是枚举两两点，根据它们的坐标和半径求出圆心的坐标，再判断所有点是否在圆内，题目不难，公式较繁，细心点就行了，还有要注意至少能选一个点，以及斜率不存在等等边界的情况，我就wa了很多次……
      时间的话，有O(n^2lgn)的，网上搜到，看了下，是把每个点作为圆心，再求每个圆与其它圆的交，记录交点，再经过处理就可以得到在同一个圆内的点数，感觉也蛮繁的，就没去实现了……有兴趣自已搜，至于那些个100ms的大牛们什么思路，我也就不得得知了……

原来在文章里转的，现在放到计算几何专题中来：

计算几何题的特点与做题要领：

1.大部分不会很难，少部分题目思路很巧妙

2.做计算几何题目，模板很重要，模板必须高度可靠。

3.要注意代码的组织，因为计算几何的题目很容易上两百行代码，里面大部分是模板。如果代码一片混乱，那么会严重影响做题正确率。

4.注意精度控制。

5.能用整数的地方尽量用整数，要想到扩大数据的方法（扩大一倍，或扩大sqrt2）。因为整数不用考虑浮点误差，而且运算比浮点快。

一。点，线，面，形基本关系，点积叉积的理解

POJ 2318 TOYS（推荐）

http://acm.pku.edu.cn/JudgeOnline/problem?id=2318

POJ 2398 Toy Storage（推荐）

http://acm.pku.edu.cn/JudgeOnline/problem?id=2398

一个矩形，有被若干直线分成N个格子，给出一个点的坐标，问你该点位于哪个点中。

知识点：其实就是点在凸四边形内的判断，若利用叉积的性质，可以二分求解。

POJ 3304 Segments

http://acm.pku.edu.cn/JudgeOnline/problem?id=3304

知识点：线段与直线相交，注意枚举时重合点的处理

POJ 1269 Intersecting Lines

http://acm.pku.edu.cn/JudgeOnline/problem?id=1269

知识点：直线相交判断，求相交交点

POJ 1556 The Doors （推荐）

http://acm.pku.edu.cn/JudgeOnline/problem?id=1556

知识点：简单图论＋简单计算几何，先求线段相交，然后再用Dij求最短路。

POJ 2653 Pick-up sticks

http://acm.pku.edu.cn/JudgeOnline/problem?id=2653

知识点：还是线段相交判断

POJ 1066 Treasure Hunt

http://acm.pku.edu.cn/JudgeOnline/problem?id=1066

知识点：线段相交判断，不过必须先理解“走最少的门”是怎么一回事。

POJ 1410 Intersection

http://acm.pku.edu.cn/JudgeOnline/problem?id=1410

知识点：线段与矩形相交。正确理解题意中相交的定义。

详见：http://hi.baidu.com/novosbirsk/blog/item/68c682c67e8d1f1d9d163df0.html

POJ 1696 Space Ant （推荐）

http://acm.pku.edu.cn/JudgeOnline/problem?id=1696

德黑兰赛区的好题目。需要理解点积叉积的性质

POJ 3347 Kadj Squares

http://acm.pku.edu.cn/JudgeOnline/problem?id=3347

本人的方法极度猥琐。复杂的线段相交问题。这个题目是计算几何的扩大数据运算的典型应用，扩大根号2倍之后就避免了小数。

POJ 2826 An Easy Problem?! （推荐）

http://acm.pku.edu.cn/JudgeOnline/problem?id=2826

问：两条直线组成一个图形，能容纳多少雨水。很不简单的Easy Problem，要考虑所有情况。你不看discuss看看能否AC。（本人基本不能）提示一下，水是从天空垂直落下的。

POJ 1039 Pipe

http://acm.pku.edu.cn/JudgeOnline/problem?id=1039

又是线段与直线相交的判断，再加上枚举的思想即可。

POJ 3449 Geometric Shapes

http://acm.pku.edu.cn/JudgeOnline/problem?id=3449

判断几何体是否相交，不过输入输出很恶心。

此外，还有一个知识点，就是给出一个正方形（边不与轴平行）的两个对角线上的顶点，需要你求出另外两个点。必须掌握其方法。

POJ 1584 A Round Peg in a Ground Hole

http://acm.pku.edu.cn/JudgeOnline/problem?id=1584

知识点：点到直线距离，圆与多边形相交，多边形是否为凸

POJ 2074 Line of Sight （推荐）

http://acm.pku.edu.cn/JudgeOnline/problem?id=2074

与视线问题的解法，关键是求过两点的直线方程，以及直线与线段的交点。数据有一个trick，要小心。

二。凸包问题

POJ 1113 Wall

http://acm.pku.edu.cn/JudgeOnline/problem?id=1113

知识点：赤裸裸的凸包问题，凸包周长加上圆周。

POJ 2007 Scrambled Polygon

http://acm.pku.edu.cn/JudgeOnline/problem?id=2007

知识点：凸包，按极角序输出方案

POJ 1873 The Fortified Forest （推荐）

http://acm.pku.edu.cn/JudgeOnline/problem?id=1873

World Final的水题，先求凸包，然后再搜索。由于规模不大，可以使用位运算枚举。

详见：http://hi.baidu.com/novosbirsk/blog/item/333abd54c7f22c52574e0067.html

POJ 1228 Grandpa's Estate （推荐）

http://acm.pku.edu.cn/JudgeOnline/problem?id=1228

求凸包顶点数目，很多人求凸包的模板是会多出点的，虽然求面积时能得到正确答案，但是在这个题目就会出问题。此外，还要正确理解凸包的性质。

POJ 3348 Cows

http://acm.pku.edu.cn/JudgeOnline/problem?id=3348

凸包面积计算

三。面积问题，公式问题

POJ 1654 Area

http://acm.pku.edu.cn/JudgeOnline/problem?id=1654

知识点：利用有向面积（叉积）计算多边形面积

POJ 1265 Area

http://acm.pku.edu.cn/JudgeOnline/problem?id=1265

POJ 2954 Triangle

http://acm.pku.edu.cn/JudgeOnline/problem?id=2954

Pick公式的应用，多边形与整点的关系。（存在一个GCD的关系，即在两点（x1，y1），（x2，y2）连线之间的整点个数（包含一个端点）为：gcd（|x1－x2|，|y1－y2|）；）

四。半平面交

半平面交的主要应用是判断多边形是否存在核，还可以解决一些与线性方程组可行区域相关的问题（就是高中时的那些）。

POJ 3335 Rotating Scoreboard

http://acm.pku.edu.cn/JudgeOnline/problem?id=3335

POJ 3130 How I Mathematician Wonder What You Are!

http://acm.pku.edu.cn/JudgeOnline/problem?id=3130

POJ 1474 Video Surveillance

http://acm.pku.edu.cn/JudgeOnline/problem?id=1474

知识点：半平面交求多边形的核，存在性判断

POJ 1279 Art Gallery

http://acm.pku.edu.cn/JudgeOnline/problem?id=1279

半平面交求多边形的核，求核的面积

POJ 3525 Most Distant Point from the Sea （推荐）

http://acm.pku.edu.cn/JudgeOnline/problem?id=3525

给出一个多边形，求里面的一个点，其距离离多边形的边界最远，也就是多边形中最大半径圆。

可以使用半平面交+二分法解。二分这个距离，边向内逼近，直到达到精度。

POJ 3384 Feng Shui （推荐）

http://acm.pku.edu.cn/JudgeOnline/problem?id=3384

半平面交实际应用，用两个圆覆盖一个多边形，问最多能覆盖多边形的面积。

解法：用半平面交将多边形的每条边一起向“内”推进R，得到新的多边形，然后求多边形的最远两点。

POJ 1755 Triathlon （推荐）

http://acm.pku.edu.cn/JudgeOnline/problem?id=1755

半平面交判断不等式是否有解。注意不等式在转化时正负号的选择，这直接影响到半平面交的方向。

POJ 2540 Hotter Colder

http://acm.pku.edu.cn/JudgeOnline/problem?id=2540

半平面交求线性规划可行区域的面积。

POJ 2451 Uyuw's Concert

http://acm.pku.edu.cn/JudgeOnline/problem?id=2451

Zzy专为他那篇nlogn算法解决半平面交问题的论文而出的题目。

五。计算几何背景，实际上解题的关键是其他问题（数据结构、组合数学，或者是枚举思想）

若干道经典的离散化＋扫描线的题目，ACM选手必做题目

POJ 1151 Atlantis （推荐）

http://acm.pku.edu.cn/JudgeOnline/problem?id=1151

POJ 1389 Area of Simple Polygons

http://acm.pku.edu.cn/JudgeOnline/problem?id=1389

矩形离散化，线段树处理，矩形面积求交

POJ 1177 Picture （推荐）

http://acm.pku.edu.cn/JudgeOnline/problem?id=1177

矩形离散化，线段树处理，矩形交的周长，这个题目的数据比较强。线段树必须高效。

POJ 3565 Ants （推荐）

http://acm.pku.edu.cn/JudgeOnline/problem?id=3565

计算几何中的调整思想，有点像排序。要用到线段相交的判断。

详见：http://hi.baidu.com/novosbirsk/blog/item/fb668cf0f362bec47931aae2.html

POJ 3695 Rectangles   

http://acm.pku.edu.cn/JudgeOnline/problem?id=3695

又是矩形交的面积，但是由于是多次查询，而且矩形不多，使用组合数学中的容斥原理解决之最适合。线段树是通法，但是除了线段树，还有其他可行的方法。

POJ 2002 Squares   

http://acm.pku.edu.cn/JudgeOnline/problem?id=2002

枚举思想，求平面上若干个点最多能组成多少个正方形，点的Hash

POJ 1434 Fill the Cisterns!（推荐）

http://acm.pku.edu.cn/JudgeOnline/problem?id=1434

一开始发昏了，准备弄个线段树。其实只是个简单的二分。

六。随机算法

POJ 2420 A Star not a Tree?

http://acm.pku.edu.cn/JudgeOnline/problem?id=2420

多边形的费马点。所谓费马点，就是多边形中一个点P，该点到其他点的距离之和最短。四边形以上的多边形没有公式求费马点，因此可以使用随机化变步长贪心法。

详见：http://hi.baidu.com/novosbirsk/blog/item/75983f138499f825dd54019b.html

七。解析几何

这种题目本人不擅长，所以做得不多，模板很重要。当然，熟练运用叉积、点积的性质还是很有用的。

POJ 1375 Intervals

http://acm.pku.edu.cn/JudgeOnline/problem?id=1375

知识点：过圆外一点求与圆的切线

POJ 1329 Circle Through Three Points   

http://acm.pku.edu.cn/JudgeOnline/problem?id=1329

求三角形外接圆

POJ 2354 Titanic

http://acm.pku.edu.cn/JudgeOnline/problem?id=2354

求球面上两个点的距离，而且给的是地理经纬坐标。

POJ 1106 Transmitters

http://acm.pku.edu.cn/JudgeOnline/problem?id=1106

角度排序，知道斜率求角度，使用atan函数。

POJ 1673 EXOCENTER OF A TRIANGLE

http://acm.pku.edu.cn/JudgeOnline/problem?id=1673

可以转化为三角形的垂心问题。

八。旋转卡壳

POJ 2187 Beauty Contest

http://acm.pku.edu.cn/JudgeOnline/problem?id=2187

凸包求最远点对。可以暴力枚举，也可以使用旋转卡壳。

POJ 3608 Bridge Across Islands（难）

http://acm.pku.edu.cn/JudgeOnline/problem?id=3608

两个凸包的最近距离。本人的卡壳始终WA。郁闷。

九。其他问题

POJ 1981 Circle and Points

http://acm.pku.edu.cn/JudgeOnline/problem?id=1981

求单位圆最多能覆盖平面上多少个点

      这题是判断线段相交，我的做法是枚举，由于题目数据中除了宝藏所在的点Point tar是浮点数，其余坐标全为整数，因此我采用的方法是把最外层每条边上的坐标的x或y坐标记录下来并排序，比如记录x=0的所有的点的y坐标在up[]数组中，其中，up[0]初始化为0。排序后，对每个数组中元素，将tar与(0,up[i]+0.5)组成一条边，判断它与每条边的交点数目即可，最后结果取最小值。
      由于边的数目较小，因此这样做也蛮快的~~
      代码copy下模板的就好了，注意，没有三面墙在同一交点，也就是说不存在不规范相交的情况，模板可以适当的改动~~

      这题应该是搜索吧，可是分类里分成了计算几何，哎，就发这吧~~
      比较需要注意的是它能成为三角形要看原图的……不过这也减小了难度，本来是要上下搜的~~
      搜索的策略是距开始的小三角为偶数的时候向上搜，否则向下搜，注意到搜索时底边只能为奇数，目标是找到最大的底边。

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

char tri[101][201];
int n;
bool Search( int flg, int a, int b, int l ){
    if( (l&1)==0 )    return false;
    int i, j;
    if( flg&1 ){
        if( l/2> a )    return false;
        for( i= a-1; i>= a-l/2; i-- )
            for( j= b+a-i; j< b+l-a+i; j++ )
                if( tri[i][j]!='-' )    return false;
    }
    else{
        if( l/2> n-a-1 )    return false;
        for( i= a+1; i<= a+l/2; i++ )
            for( j= b+i-a; j< b+l-i+a; j++ )
                if( tri[i][j]!='-' )    return false;
    }
    return true;
}
int main(){
    int i, j, k, max, t= 1;
    while( scanf("%d",&n) && n ){
        max= 0;
        getchar();
        for( i= 0; i< n; i++ )
            gets(tri[i]);
        for( i= 0; i< n; i++ ){
            if( n-i<= max/2 )    break;
            for( j= i, k= 0; j< 2*n-i-1; j++ ){
                if( tri[i][j]=='-' ){
                    k++;
                    if( (k&1) && k> max )
                        if( Search(i+j,i,j-k+1,k) )    max= k;
                        else    k--;
                }
                else    k= 0;
            }
        }
        printf("Triangle #%d\nThe largest triangle area is %d.\n\n",t++,(max+1)*(max+1)/4);
    }
    return 0;
}

      这题乍一看感觉很轻易啊，简单的判断线段是否相交，可是wa了N次，还以为自已敲的模板有问题，看了Discuss以后才发现，这题玩了点语义的陷阱，一个是我自已没注意，长方形是实心的！另外一个是左上点的x未必小于右下点的x……
      改改就好了，可是这种题……太无语了~~
      代码就不发了，用这题测试了下自已的模板，就只发个模板了，在模板里找~~

      这题和PKU 1151几乎是一样的，只是数据量和类型有些差别，之所以再贴这题，是因为学习了下Felicia大牛的代码，果然比我的简单很多很多……
      下面解释下代码的意思，大体思路和我是一样的，只是实现的时候很巧妙，首先，他把一个矩形分成两部分记录，以y坐标作为关键字，用flag表示是上面的还是下面的y坐标，这样，他排序只进行了两次，一次对所有的矩形信息排序，一次对所有的x区间排序，由于计算的时候其实是和x坐标的顺序没有关系的，我自已写的那个程序排序等于是浪费了……他的去重也很强悍，调用unique()函数去重，返回末尾元素的指针，再减去数组首指针，得到数组的大小~~最后求每一段的面积的时候，他又用了点小技巧，由于矩形信息是按y坐标排好序的，因此如果当前进来的坐标是flag=0的坐标的话，说明它比当前最小的y坐标要大，把这个矩形加到当前的“队列”中来，cnt++，如果当前进来的坐标是flag=1的坐标的话，说明有一个矩形已经结束了，cnt--，当cnt减到0且进来的是flag=0的坐标的话，说明当前最小的y坐标也比这个矩形最大的y坐标要大，故重新建立“队列”，并更新area值。
      下面是他的代码，有改动。

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 4010;

typedef struct line_t{
    int l, r, y;
    int flag;
};

bool operator <(const line_t &a, const line_t &b){
    return a.y < b.y;
}

bool d_equal(const int &a, const int &b){
    return abs(a - b) < 1e-9;
}

int n;
int x[maxn];
int cnt_x, cnt_line;
line_t line[maxn];

int main(){
    while (1){
        cnt_x = 0;
        cnt_line = 0;
        while (1){
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            if (x1 == -1) break;
            x[cnt_x++] = x1;
            x[cnt_x++] = x2;
            line[cnt_line].flag = 0;
            line[cnt_line].l = x1;
            line[cnt_line].r = x2;
            line[cnt_line++].y = y1;
            line[cnt_line].flag = 1;
            line[cnt_line].l = x1;
            line[cnt_line].r = x2;
            line[cnt_line++].y = y2;
        }
        sort(line, line + cnt_line);
        sort(x, x + cnt_x);
        cnt_x = unique(x, x + cnt_x, d_equal) - x;
        if (cnt_x == 0) break;
        int area = 0;
        for (int i = 0; i < cnt_x - 1; i++){
            int cnt = 0;
            int now_y;
            for (int j = 0; j < cnt_line; j++) if (line[j].l <= x[i] && line[j].r >= x[i + 1]){
                if (cnt == 0) now_y = line[j].y;
                if (line[j].flag == 0) cnt++;
                else cnt--;
                if (cnt == 0) area += (x[i + 1] - x[i]) * (line[j].y - now_y);
            }
        }
        printf("%d\n", area);
    }
    return 0;
}

      求N个点中的任意两点的最大距离，先求凸包O(nlgn)，再用旋转卡壳O(n)，可惜的是，我现在还不会旋转卡壳，先发个枚举的代码，O(n2)的……也能过~~

#include <iostream>
#include <cmath>
using namespace std;
#define eps 1e-8
struct Point{int x,y;};
Point org[50001], stk[50001];
//计算cross product (P1-P0)x(P2-P0)
int Xmult(Point p1,Point p2,Point p0){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
//Graham_Scan算法顺时针构造包含所有共线点的凸包,O(nlogn)
Point p1,p2;
int graham_cp(const void* a,const void* b){
    int ret=Xmult(*((Point*)a),*((Point*)b),p1);
    return (ret==0)?(Xmult(*((Point*)a),*((Point*)b),p2)>0?1:-1):(ret>0?1:-1);
}
void _graham(int n,Point* pt,int& s,Point* ch){
    int i,k=0;
    for (p1=p2=pt[0],i=1;i<n;p2.x+=pt[i].x,p2.y+=pt[i].y,i++)
        if (p1.y-pt[i].y>eps||((p1.y-pt[i].y==0)&&p1.x>pt[i].x))
            p1=pt[k=i];
    p2.x/=n,p2.y/=n;
    pt[k]=pt[0],pt[0]=p1;
    qsort(pt+1,n-1,sizeof(Point),graham_cp);
    for (ch[0]=pt[0],ch[1]=pt[1],ch[2]=pt[2],s=i=3;i<n;ch[s++]=pt[i++])
        for (;s>2&&Xmult(ch[s-2],pt[i],ch[s-1])<-eps;s--);
}
//原始点集pt，凸包点集convex，返回凸包点集大小
int Graham_Scan(int n,Point* pt,Point* convex,int iscollinear=1,int isclockwise=1){
    Point* temp=new Point[n];
    int s,i;
    _graham(n,pt,s,temp);
    for (convex[0]=temp[0],n=1,i=(isclockwise?1:(s-1));isclockwise?(i<s):i;i+=(isclockwise?1:-1))
        if (iscollinear||Xmult(temp[i-1],temp[i],temp[(i+1)%s])!=0)
            convex[n++]=temp[i];
    delete []temp;
    return n;
}
int main(){
    int n, i, j, max= 0, tmp;
    scanf("%d",&n);
    for( i= 0; i< n; i++ )
        scanf("%d%d",&org[i].x,&org[i].y);
    n= Graham_Scan(n,org,stk);
    for( i= 0; i< n; i++ )
        for( j= i+1; j< n; j++ ){
            tmp= (stk[i].x-stk[j].x)*(stk[i].x-stk[j].x)+(stk[i].y-stk[j].y)*(stk[i].y-stk[j].y);
            if( tmp> max )    max= tmp;
        }
    printf("%d\n",max);
    return 0;
}

      这道题目用了蛮多结论的，要求格子面上多边形的边上点数，内部点数和占的面积，用到的结论：
      1.以格子点为顶点的线段，覆盖的点的个数为GCD(dx,dy)，其中，dxdy分别为线段横向占的点数和纵向占的点数。如果dx或dy为0，则覆盖的点数为dy或dx。
      2.Pick公式：平面上以格子点为顶点的简单多边形，如果边上的点数为on，内部的点数为in，则它的面积为A=on/2+in-1。（http://episte.math.ntu.edu.tw/articles/sm/sm_25_10_1/index.html有证明和推导）
      3.任意一个多边形的面积等于按顺序求相邻两个点与原点组成的向量的叉积之和（黑书上有说明）
      下面是我的实现代码：

#include <iostream>
using namespace std;

int Gcd( int a, int b ){    //a, b为两个输入的数，返回最大公约数
    while( b!= 0 ){
        int r= b;
        b= a % b;
        a= r;
    }
    return a;
}
int main(){
    int i, k, t, n, x[101], y[101], dx, dy, on, in, area;
    scanf("%d",&t);
    for( k= 1; k<= t; k++ ){
        scanf("%d",&n);
        for( i= 1, on=area=x[0]=y[0]= 0; i<= n; i++ ){
            scanf("%d%d",&dx,&dy);
            x[i]= dx+ x[i-1];
            y[i]= dy+ y[i-1];
            on+= Gcd(abs(dx),abs(dy));
            area+= x[i-1]*y[i]-x[i]*y[i-1];
        }
        in= ( area- on+ 2 )/ 2;
        printf("Scenario #%d:\n%d %d %.1lf\n\n",k,in,on,area/2.0);
    }
    return 0;
}

      这道题和黑书上在线段树那一部分举的火星地图的例子差不多，不过这题数据量很小，不用线段树做。
      首先离散化，我觉得自已离散化的方法很CUO，用了类似归并排序的方法把所有的x坐标去重排序后放在corx[]中，然后再对每一段计算面积，计算面积的时候我又对y坐标进行了一次排序，做的很繁，不知道大牛们是怎么离散化的，去学习学习~~
      先发下我的代码：

#include <iostream>
#include <algorithm>
using namespace std;

int n;
struct Rectangle{
    double x1, y1, x2, y2;
}rec[101];
bool cmp( Rectangle r1, Rectangle r2 ){
    if( r1.x1< r2.x1 )    return true;
    else if( r1.x1> r2.x1 )    return false;
    if( r1.y1> r2.y1 )    return true;
    else if( r2.y1< r2.y1 )    return false;
    if( r1.x2< r2.x2 )    return true;
    else if( r1.x2> r2.x2 )    return false;
    if( r1.y2> r2.y2 )    return true;
    return false;
}
struct Ycor{
    double max, min;
}ycor[101];
bool cmp2( Ycor y1, Ycor y2 ){
    return y1.max>y2.max || (y1.max==y2.max&&y1.min<y2.min);
}
int main(){
    int i, j, k, l, t= 1;
    double corx[201], tmp[101], area, ymax, ymin;
    while( scanf("%d",&n) && n ){
        area= 0;
        for( i= 0; i< n; i++ ){
            scanf("%lf%lf%lf%lf",&rec[i].x1,&rec[i].y1,&rec[i].x2,&rec[i].y2);
            tmp[i]= rec[i].x2;
        }
        sort(rec,rec+n,cmp);
        sort(tmp,tmp+n);
        for( i= 0, j= 0, k= 0; i< n && j< n; ){
            if( rec[i].x1< tmp[j] ){
                if( corx[k-1]!= rec[i].x1 )
                    corx[k++]= rec[i].x1;
                i++;
            }
            else if( rec[i].x1> tmp[j] ){
                if( corx[k-1]!=tmp[j] )
                    corx[k++]= tmp[j];
                j++;
            }
            else{
                if( corx[k-1]!=tmp[j] )
                    corx[k++]= tmp[j];
                i++, j++;
            }
        }
        while( i< n )    corx[k++]= rec[i++].x1;
        while( j< n )    corx[k++]= tmp[j++];
        for( i= 1; i< k; i++ ){
            ycor[0].max= ycor[0].min= 0;
            for( j= 0, l= 0; j< n; j++ )
                if( rec[j].x1<=corx[i-1] && rec[j].x2>=corx[i] )
                    ycor[l].max= rec[j].y2, ycor[l++].min= rec[j].y1;
            sort(ycor,ycor+l,cmp2);
            ymax= ycor[0].max, ymin= ycor[0].min;
            for( j= 1; j< l; j++ ){
                if( ycor[j].max< ymin ){
                    area+= (corx[i]-corx[i-1])*(ymax-ymin);
                    ymax= ycor[j].max, ymin= ycor[j].min;
                }
                else if( ycor[j].min< ymin )    ymin= ycor[j].min;
            }
            area+= (corx[i]-corx[i-1])*(ymax-ymin);
        }
        printf("Test case #%d\nTotal explored area: %.2lf\n\n",t++,area);
    }
    return 0;
}

      很典型的凸包问题。我一开始想繁了，因为我想如果是个凹多边形，可能最终的围墙也可能是凹的，后来想起题中的要求是最小的长度，而凹的围墙虽然离castle距离精确的等于r，可是长度并不是最小的，只有凸包的长度才是最小的。因此问题就简单很多，先求凸包，再求所有边的长度和，最后加上一个2*PI*r，这是所有凸包点处的弧的长度和。
      代码我就不发了，因为我是用的模板，关键代码没自已写，顺便也测试下模板正确性。

Graham-Scan法求凸包（代码copy自浙大模板）

#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
struct Point{double x,y;};
Point pt[1001], stk[1001];
//计算cross product (P1-P0)x(P2-P0)
double Xmult(Point p1,Point p2,Point p0){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
//Graham_Scan算法顺时针构造包含所有共线点的凸包,O(nlogn)
Point p1,p2;
int graham_cp(const void* a,const void* b){
    double ret=Xmult(*((Point*)a),*((Point*)b),p1);
    return zero(ret)?(Xmult(*((Point*)a),*((Point*)b),p2)>0?1:-1):(ret>0?1:-1);
}
void _graham(int n,Point* pt,int& s,Point* ch){
    int i,k=0;
    for (p1=p2=pt[0],i=1;i<n;p2.x+=pt[i].x,p2.y+=pt[i].y,i++)
        if (p1.y-pt[i].y>eps||(zero(p1.y-pt[i].y)&&p1.x>pt[i].x))
            p1=pt[k=i];
    p2.x/=n,p2.y/=n;
    pt[k]=pt[0],pt[0]=p1;
    qsort(pt+1,n-1,sizeof(Point),graham_cp);
    for (ch[0]=pt[0],ch[1]=pt[1],ch[2]=pt[2],s=i=3;i<n;ch[s++]=pt[i++])
        for (;s>2&&Xmult(ch[s-2],pt[i],ch[s-1])<-eps;s--);
}
//原始点集pt，凸包点集convex，返回凸包点集大小
int Graham_Scan(int n,Point* pt,Point* convex,int iscollinear=1,int isclockwise=1){
    Point* temp=new Point[n];
    int s,i;
    _graham(n,pt,s,temp);
    for (convex[0]=temp[0],n=1,i=(isclockwise?1:(s-1));isclockwise?(i<s):i;i+=(isclockwise?1:-1))
        if (iscollinear||!zero(Xmult(temp[i-1],temp[i],temp[(i+1)%s])))
            convex[n++]=temp[i];
    delete []temp;
    return n;
}

判断线段是否相交（包括规范相交），如果相交，求出交点，代码参考黑书。

#define Type int
#define fab(x) abs(x)
#define eps 1e-8
struct Point{
    Type x, y;
};
int cmp( Type d ){
    if( fab(d)< eps )    return 0;
    return (d>0?1:-1);
}
int xyCmp( Type p, Type mini, Type maxi ){
    return cmp(p-mini)*cmp(p-maxi);
}
int betweenCmp( Point a, Point b, Point c ){
    if( fab(b.x-c.x)> fab(b.y-c.y) )
        return xyCmp(a.x,min(b.x,c.x),max(b.x,c.x));
    else
        return xyCmp(a.y,min(b.y,c.y),max(b.y,c.y));
}
Type det( Type x1, Type y1, Type x2, Type y2 ){
    return x1*y2-x2*y1;
}
Type cross( Point a, Point b, Point c ){
    return det(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);
}
int SegCross( Point a, Point b, Point c, Point d, Point& p ){
    Type s1, s2, s3, s4;
    int d1= cmp(s1=cross(a,b,c));
    int d2= cmp(s2=cross(a,b,d));
    int d3= cmp(s3=cross(c,d,a));
    int d4= cmp(s4=cross(c,d,b));
    //规范相交求交点
    if( (d1^d2)==-2 && (d3^d4)==-2 ){
        p.x= ( c.x*s2-d.x*s1 )/ ( s2-s1 );
        p.y= ( c.y*s2-d.y*s1 )/ ( s2-s1 );
        return 1;
    }
    //判定非规范相交
    if( d1==0 && betweenCmp(c,a,b)<=0 ||
        d2==0 && betweenCmp(d,a,b)<=0 ||
        d3==0 && betweenCmp(a,c,d)<=0 ||
        d4==0 && betweenCmp(b,c,d)<=0 )
        return 2;
    return 0;
}

      网上都评价说这题不难，没什么算法，是道水题，可是我看了别人的代码后，感觉收获还是比较大的，就发了。
      这题先是求积分，高中物理都能搞定的，把dl=rdă代入就能求得I=ă*k*h，其中ă是每条边对原点夹的角，比如对边AB，它的ă就是<AOB。那么下面的问题就转化为整个图形对原点所夹的角的最大值，这里可能有个问题，比如对于一个螺旋型的Fence，原点在中心，那么可能求出的夹角大于2*PI，由于Fence是不能透光、反射、散射的，因此最大值只能为2*PI。又由于Fence不能经过原点，因此每条边的夹角在-PI~PI之间，这里求整个图形对原点所夹的角用了一个很强的方法，可以保证无论从哪个点开始算，只要是按顺序，它一定能求得最大的角度(我领悟了半天啊)，而且min一定要初始化为0而不是2*PI等大于0的数，考虑下原点在图形内部的情况就知道了~~至于正确性，可以自已画个图就能理解了~~
      下面是我的实现代码，参考了网上代码~~

#include <iostream>
#include <cmath>
using namespace std;
#define PI 3.1415926
double Angle( double x0, double y0, double x1, double y1 ){
     double a= atan2(y0,x0);
     double b= atan2(y1,x1);
     if( b-a> PI ) a+= 2*PI;    //将夹角映射到-PI~PI之间
     if( a-b> PI ) b+= 2*PI;
     return a-b;
}

int main(){
    double h, k, x[101], y[101], max= 0, min= 0, sum= 0;
    int n, i;
    scanf("%lf%lf%d",&k,&h,&n);
    for( i= 0; i< n; i++ )
        scanf("%lf%lf",&x[i],&y[i]);
    x[n]= x[0], y[n]= y[0];
    for( i= 0; i< n; i++ ){      //精髓啊
        sum+= Angle(x[i],y[i],x[i+1],y[i+1]);
        if( sum< min )    min= sum;
        if( sum> max )    max= sum;
        if( max-min>= 2*PI ){
            max= min+ 2*PI;
            break;
        }
    }
    printf("%.2lf\n",(max-min)*k*h);
    return 0;
}

      也不知道最近是不是有人在攻POJ，怎么老是当掉啊~~昨天当了两次，今天刚写好一交又当掉了，真郁闷……北大那么有钱，就多投点啊，买个无敌的服务器，好歹也算中国最大的OJ了啊，老发生这种事情~~
      愤怒下，BS下，继续写……

      今天万里无云，什么叫万里无云，这真的是一点云也看不到啊，连只苍蝇也看不到……

      从上次万里无云说起吧，那天心情很好，令人身心俱霉的烂冬天气终于结束了，我吃过晚饭，去九龙湖畔吹吹风，看看夕阳，走去的，路还蛮远的，在湖边的小桥上，看着鸳鸯戏水（也可能是别的什么鸟），看着夕阳西沉，感觉很宁静，只是奇怪的是夕阳的确沉下去了，问题是沉的那么早？我几番看表，都是5点多，时间有时候过的就是慢……
      就这样，我傻B的在那边吹风吹到8点多（还是看手机短信才发现表停了）……

      后来也不想看书了，就去图书馆逛逛吧，我那天特别走运，一去就找到了我一直想找的书，我那天特别不走运，在准备去借书的时候把那本书当成另一本没用的书恭恭敬敬的放回了书架(回去我还以为我书弄丢了，直到发现那本没用的书)……

       再后来的一天中午，说是要卫生检查，听说辅导员可能要来，就大家一起抱个佛脚，把宿舍从里到翻新了一下，结果来的是两个女生……心想太没价值了，大呼：“梅梅怎么不来啊！“梅梅这个时候出现了（梅梅是我们辅导员……关键是她比我妈还大）……

      还是那天中午，和雨帮同学开党员群众座谈会，我们把群众意见收集来了后去教室写，安静点嘛，等我甩腿到了教室，突然发现我没有信纸……四处借，借不到……回宿舍……时光是怎样匆匆流走的？我心里有自已的看法了……

      继续，写完报告就要交，谁交呢？我自已想去交，因为我正好找辅导员有事，但就这么去了？不是我风格……我找到雨，他在补眠，正好。“报告我写好啦，你去交吧？”“Eng en en……”，嘿嘿，“那我交？”“恩！”“有什么好处不？”他来劲了坐起来和我把几乎从大一的账拿出来一笔一笔的算，算到一半的时候我悄无声息的溜出去了……自讨没趣……

      我4点去辅导员办公室，那时天一阵雨一阵阴，我心想，速度去，办完事速度回！就骑了个车子冲到系办，结果，辅导员给四班开班会去了！而且才去不久。怎么办？等？不是我风格！我正好可以去把图书馆那本书再借回来嘛！我想它应该还在我放的位置上吧，就再骑个车子去借书，反正要等辅导员，不急，慢慢来，晃到图书馆，慢悠悠借到书，真是顺利啊，出门，下起了雨……怎么办？手上有书，还有伞，还要扶车，我没这技术，算了，果断点，走！我急匆匆的走到系办，已经5点了，辅导员再拖也该结束了吧！我对了，的确结束了，而且早就结束了，她已经回家了……天啊，怎么这么背啊，我出门，雨停了……

      怎么办？回图书馆拿车？那么远，算了吧，还是去吃饭吧，下次有空再去拿，路过教学楼，顺便把书和伞放下，带那么多东西不方便啊，再说可能下雨吗？……可能！我吃完饭，淋着雨回来了……

      怎么说那天心情都不太好，自习到10点多，回宿舍开黑（三个人手机上网QQ升级，两人一家，还有一个当奸细），想发泄下，我和小宝是一家，配合的很好，室长在对家，和我们配合的也很好……可是打牌，不仅要看配合，更要看手气啊，那天我输的郁郁而睡……

      第二天早上起来，发现手机没电了，就在留在宿舍充电。上完课回来，速度要用手机。开机，自动关闭
      ？
      再开机，再自动关闭
      ！
      把充电器插头弄弄，手机插上去，没反应
      ？
      换个插座，还是没反应
      ！
      Shit！充电器怎么这个时候坏？！嗨，算了，去教室了，在电脑上面充吧……

      下午写写程序，晚上吃完晚饭看到老爸在线，心想他打牌那么厉害，跟他蹭点分吧，开黑！可是这个世界就是这样，永远都有拆黑的同志，我们一上来就被打了两个光头……看着我从有车一族一路跌回赤脚，我心寒了。“老爸，我有点困了，你自已玩吧……”

      晚上回宿舍，一如既往的Dota开黑，一如既往的被拆……宿舍四口郁郁而睡……

      今天早上一觉醒来，万里无云，为什么呢？因为我跟别人说今天肯定下雨。为什么我这么说呢？因为我们班本来组织今天去春游，前不久和小朱约好去春游就是因为连下了2个多星期的雨而不了了之，根据经验，我下了这样的论断，即我们肯定去不了。我对了，因为我们没去成；我错了，因为没去成的原因是钱没谈好……

      嗨，天晴了，心情也好些了，好好努力吧！