1800: [Ahoi2009]fly 飞行棋

BZOJ1800..
(BZOJ上数据范围太小了,这个题有O(n)做法)
首先可知矩形的对角线一定是圆的直径,而且任意两条直径一定可以确定一个矩形
只需求出圆的所有直径个数,任选两条即可(C(x,2),其中x为直径个数)
 
关于圆的直径个数,可知直径的两端点一定是这个圆上的最远点对,旋转卡壳就好...
 
代码如下:(这个是O(n ^ 2)的做法,即暴力枚举对角线)

#include <stdio.h>

#include <iostream>

#include <set>

#include <algorithm>

 

typedef long long Long;

 

Long get_int()

{

    Long r = 0;

    char c = 0;

    do

    {

        c = getchar();

    }

    while(c == ' ' || c == '\n' || c == '\t');

 

    do

    {

        r *= 10LL;

        r += (Long)(c - '0');

        c = getchar();

    }

    while(c >= '0' && c <= '9');

    return r;

}

 

const int N = 20100;

 

Long p[2 * N + 100];

 

int n = 0;

 

Long sum = 0LL;

 

int main()

{

     

    scanf("%d",&n);

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

    {

        p[i] = p[i + n] = get_int();

        sum += p[i];

    }

     

    Long len = (sum >> 1);

     

    Long result = 0LL;

     

    Long now_dis = 0;

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

    {

        now_dis = 0;

        for(int q = i;q <= 2 * n;q++)

        {

            now_dis += p[q];

            if(now_dis == len)

                result++;

            if(now_dis > len)

                break;

        }

    }

     

    result >>= 1;

     

    result = (result * (result - 1)) >> 1;

     

    std::cout<<result<<std::endl;

     

    return 0;

}