hdu5785(极角排序求所有锐角钝角个数)

做法很显然，求出所有的锐角和钝角就能求出有多少个锐角三角形了。

我用了愚钝的方法，写了两三个小时。。。

看了下别人简单的代码。学习了下做法。

sort(temp+,temp+cnt+);//排序

For(j,,cnt)//这一步，复制了一遍所有角，然后就能很好的处理在逆时针的情况

{

    temp[j+cnt]=temp[j]+*PI;

}

int l=,r=,le=;

For(j,,cnt)

{

    while(temp[r]-temp[j]<PI&&r<=*cnt)r++;//找出<180的角

    while(temp[l]-temp[j]<0.5*PI&&l<=*cnt)l++;//找出<90度的角

    while(temp[le]-temp[j]<=eps&&le<=*cnt)le++;//排除一条直线的情况

    ans1=ans1+r-l;

    ans2=ans2+l-le;

}

再附上自己拙略的代码：

//

//  main.cpp

//  hdu5784

//

//  Created by New_Life on 16/8/10.

//  Copyright © 2016年 chenhuan001. All rights reserved.

//

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

using namespace std;

#define PI acos(-1.0)

struct point

{

    int x,y;

    double shita;

}g[],tg[];

int cmp(point p1,point p2)

{

    return p1.shita<p2.shita;

}

double operator*(point p1, point p2) // 计算叉乘 p1 × p2

{

    return ((long long)p1.x * p2.y - (long long)p2.x * p1.y);

}

double operator&(point p1, point p2) { // 计算点积 p1·p2

    return ((long long)p1.x * p2.x + (long long)p1.y * p2.y);

}

int dsub(int p1,int p2)

{

    return (tg[p1]*tg[p2]<=)&&( (tg[p1]&tg[p2])> );

}

int savenum[];

int main(int argc, const char * argv[]) {

    int n;

    while(cin>>n)

    {

        for(int i=;i<n;i++)

        {

            scanf("%d%d",&g[i].x,&g[i].y);

        }

        long long ans = ;

        for(int i=;i<n;i++)

        {

            int cnt = ;

            for(int j=;j<n;j++)

            {

                if(j==i) continue;

                int tx = g[j].x - g[i].x;

                int ty = g[j].y - g[i].y;

                tg[cnt].x = tx; tg[cnt].y = ty;

                tg[cnt++].shita = atan2(ty, tx);

            }

            if(cnt < ) continue;

            sort(tg,tg+cnt,cmp);

            memset(savenum,,sizeof(savenum));

            int scnt= cnt;

            int tcnt = ;

            savenum[tcnt++] = ;

            for(int j=;j<cnt;j++)

            {

                if( tg[j]*tg[tcnt-]== && ( (tg[j]&tg[tcnt-])> ) )

                {

                    savenum[tcnt-]++;

                }

                else

                {

                    tg[tcnt] = tg[j];

                    savenum[tcnt] = ;

                    tcnt++;

                }

            }

            cnt = tcnt;

            for(int j=;j<cnt;j++)

            {

                ans += savenum[j]*(savenum[j]-);

            }

            if(cnt==) continue;

            tcnt = ;

            int lf=,rt=;

            while( dsub(,lf) ){

                tcnt += savenum[lf];

                lf = (lf-+cnt)%cnt;

                if(lf == ) break;

            }

            lf = (lf+)%cnt;

            while( rt!= && dsub(rt,) ) tcnt+=savenum[rt],rt = (rt+)%cnt;

            //rt = (rt-1+cnt)%cnt;

            ans += savenum[]*(tcnt-savenum[]);

            ans -= *savenum[]*(scnt-tcnt);

            for(int j=;j<cnt;j++)

            {

                if(j == lf)

                {

                    tcnt -= savenum[lf];

                    lf = (lf+)%cnt;

                }

                if(j == rt)

                {

                    tcnt += savenum[j];

                    rt = (rt+)%cnt;

                }

                while( !dsub(j,lf) )

                {

                    tcnt -= savenum[lf];

                    lf= (lf+)%cnt;

                    //if(lf == j) break;

                }

                while(rt!=j && dsub(rt,j) ) tcnt+=savenum[rt],rt=(rt+)%cnt;

                ans += savenum[j]*(tcnt-savenum[j]);

                ans -= *savenum[j]*(scnt-tcnt);

            }

        }

        cout<<ans/<<endl;

    }

    return ;

}

/*

 4

 0 0

 0 1

 1 0

 1 1

 9

 0 0

 2 0

 0 1

 2 1

 1 0

 1 1

 0 2

 1 2

 2 2

 4

 0 0

 1 1

 2 2

 3 3

 5

 0 0

 1 1

 2 2

 -1 0

 10000 0

 */