1800: [Ahoi2009]fly 飞行棋
YYY
posted @ 2015年7月13日 15:09
with tags
旋转卡壳
, 745 阅读
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
（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;
}
评论 (0)
