注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

Axes of Symmetry([POI2007]对称轴osi)  

2012-04-01 09:03:37|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
刚才很囧地把这道题AC了……貌似网上有用KMP做的……我这个方法不用……但也能AC。
先说下题意,就是给你一个不自交、相邻两边不平行的多边形,让你求出多边形的对称轴的个数。
然后我画了几个图,发现对称轴数多余两条的多边形的对称轴总是交于一点的。证明很简单,首先对称轴不可能平行,如果平行图形就会像sinx的图像一样延伸到无穷远处。现在假设对称轴们未交于一点,那么反过来想,如果已经知道对称轴是哪几条,就可以把一个图形多次作对称变换产生出这个对称轴不交于一点的图形。那么试着画一下,就可以发现这样做对称变换完全没有尽头,产生出的是一个无穷的图!
我进一步发现,n条对称轴总是把平面分成相等2n份。证明如下:如图,如果现在已经有两条对称轴l1,l2,那么因为对称性,在l2的另一边一定存在一个l3与l1成轴对称,由此,可以继续这样在l3另一边找到一个与l2成轴对称的l4……于是,我们就可以找到PI/a这么多条对称轴(a是l1与l2的夹角)如果一开始找到的l1,l2的夹角足够小,我们完全可以通过刚才的变换找出其他所有的对称轴!
Axes of Symmetry([POI2007]对称轴osi) - vfleaking - vfleaking的博客
于是,我的算法如下……找到2条相邻的对称轴,然后拿PI除以夹角,然后cout。
那么,如何找到相邻的对称轴呢?首先,对称轴与多边形的交点一定要么是顶点要么是某条边的中点(这个显然吧),其次,对称轴两边的点数相同。由此可以顺着枚举顶点和边上中点,然后点i和点i+n/2的连线就是一条可能的对称轴(各种加1减1自己琢磨一下就出来了),然后暴力check一下。最先发现的两条对称轴一定是相邻的,于是汇报结果……

代码:(小心观看)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <complex>
#define _USE_MATH_DEFINES
#include <cmath>
using namespace std;

typedef complex<double> ComplexVector;

inline double cross(const ComplexVector &a, const ComplexVector &o, const ComplexVector &b)
{
    return (a.real() - o.real()) * (b.imag() - o.imag()) - (a.imag() - o.imag()) * (b.real() - o.real());
}
inline double dot(const ComplexVector &a, const ComplexVector &o, const ComplexVector &b)
{
    return (a.real() - o.real()) * (b.real() - o.real()) + (a.imag() - o.imag()) * (b.imag() - o.imag());
}
inline double dot(const ComplexVector &a, const ComplexVector &b)
{
    return a.real() * b.real() + a.imag() * b.imag();
}

const int MaxN = 100000;

inline int sign(const double &d)
{
    if (d > 1e-7)
        return 1;
    else if (d < -1e-7)
        return -1;
    else
        return 0;
}

template <class T>
inline T sqr(const T &a)
{
    return a * a;
}

//I'm lazy...actually, these are struct Polygon.
int n;
ComplexVector p[MaxN + 1];
inline int prev(const int &i)
{
    return i == 0 ? n - 1 : i - 1;
}
inline int next(const int &i)
{
    return i + 1 == n ? 0 : i + 1;
}

int len;
ComplexVector axesDir[2];

inline void check(const ComplexVector &target1, const ComplexVector &target2, int left, int right)
{
    ComplexVector dir = target1 - target2;
    ComplexVector t = sqr(dir/ norm(dir);
    do
    {
        ComplexVector diff = t * conj(p[left] - target2+ target2 - p[right];
        if (sign(diff.real()) != 0 || sign(diff.imag()) != 0)
            return;
        
        left = prev(left);
        right = next(right);
    }
    while (next(left!= right && next(next(left)) != right);
    
    axesDir[len++] = dir;
}

int main()
{
    freopen("1100.in", "r", stdin);
    freopen("1100.out", "w", stdout);
    
    int nCases;
    
    cin >> nCases;
    while (nCases--)
    {
        cin >> n;
        for (int i = 0i < n; i++)
            scanf("%lf %lf", &p[i].real(), &p[i].imag());
        
        len = 0;
        if (n & 1)
        {
            int oppo = n / 2;
            for (int i = 0i < n; i++, oppo = next(oppo))
            {
                check(p[i], (p[oppo] + p[next(oppo)]) / 2.0, prev(i), next(i));
                if (len == 2)
                    break;
                check((p[i] + p[next(i)]) / 2.0, p[next(oppo)], i, next(i));
                if (len == 2)
                    break;
            }
        }
        else
        {
            int oppo = n / 2;
            for (int i = 0i < n; i++, oppo = next(oppo))
            {
                check(p[i], p[oppo], prev(i), next(i));
                if (len == 2)
                    break;
                check((p[i] + p[next(i)]) / 2.0, (p[oppo] + p[next(oppo)]) / 2.0, i, next(i));
                if (len == 2)
                    break;
            }
        }
        if (len == 0)
            cout << 0 << endl;
        else
        {
            double ret = acos(dot(axesDir[0], axesDir[1]) / (abs(axesDir[0]) * abs(axesDir[1])));
            if (sign(ret== 0)
                ret = M_PI;
            cout << setiosflags(ios::fixed<< setprecision(0<< M_PI / ret << resetiosflags(ios::fixed<<setprecision(6<< endl;
        }
    }
    
    return 0;
}
  评论这张
 
阅读(1059)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017