加载中…HDU 3902 Swordsman 2011 Multi-University Training Contest 7 - Host by ECNU
(2011-08-02 18:39:17)
标签：
hdu3902swordsmanit |
分类： 计算几何 |
题目描述：
给你一个简单多边形，问你是否是轴对称的。
解题报告：
先把原来的n个点拓展，加上每条边的中点，变为2n个点，O（n）枚举每个点和它对面的点，看看重心是否在这条轴上，在的话，这条轴就有可能是对称轴，再用O（n）的时间枚举轴两端的点，看看是否被轴平分且垂直，都是的话，说明对称。
实际上就是加了“重心”这个强剪枝。
代码如下：
double
x, y;
pint(double x, double y) : x(x), y(y){}
pint(){}
pint
ret=u.a;
double
t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))
/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));
ret.x+=(u.b.x-u.a.x)*t;
ret.y+=(u.b.y-u.a.y)*t;
return
ret;
line
u,v;
u.a.x=(a.x+b.x)/2;
u.a.y=(a.y+b.y)/2;
u.b=c;
v.a.x=(a.x+c.x)/2;
v.a.y=(a.y+c.y)/2;
v.b=b;
return
intersection(u,v);
return
(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
pint
ret,t;
double
t1=0,t2;
int
i;
ret.x=ret.y=0;
for
(i=1;i<n-1;i++)
if
(fabs(t2=xmult(p[0],p[i],p[i+1]))>eps){
t=barycenter(p[0],p[i],p[i+1]);
ret.x+=t.x*t2;
ret.y+=t.y*t2;
t1+=t2;
}
if
(fabs(t1)>eps)
ret.x/=t1,ret.y/=t1;
return
ret;
return
fabs( (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y))
< eps;
//cout
<< a.x
<< ' '
<< a.y
<< endl;
//cout
<< b.x
<< ' '
<< b.y
<< endl;
double
y1 = b.y - a.y;
double
x1 = b.x - a.x;
double
y2 = d.y - c.y;
double
x2 = d.x - c.x;
double
tmp = y1 * y2 + x1 * x2;
return
fabs(tmp) < eps;
double
dis1 = (a.x - c.x) * (a.x - c.x) + (a.y - c.y) * (a.y - c.y);
double
dis2 = (b.x - c.x) * (b.x - c.x) + (b.y - c.y) * (b.y - c.y);
//cout
<< dis1
<< ' '
<< dis2
<< endl;
return
fabs(dis1 - dis2) < eps;
while(scanf("%d", &n) !=
EOF)
{
for(int i = 0; i
< n; i++)
scanf("%lf%lf", &jeo[i].x,
&jeo[i].y);
pint tar = barycenter(n,
jeo);
int cnt = 0;
for(int i = 0; i
< n; i++)
{
jeogia[cnt++] = jeo[i];
int next = (i + 1);
if (next == n) next = 0;
jeogia[cnt++] = pint((jeo[i].x + jeo[next].x) *
0.5, (jeo[i].y + jeo[next].y) * 0.5);
}
bool flag = false;
for(int i = 0; i
< n; i++)
{
int next = i + n;
if (sameline(tar, jeogia[i], jeogia[i +
n]))
{
int left,
right;
if (i
& 1)
{
left = i / 2;
right = (left + 1) % n;
}
else
{
left = (i / 2 - 1 + n) % n,
right = (i / 2 + 1) % n;
}
//int left
= (i / 2 - 1 + n) % n, right = (i / 2 + 1) % n;
int pre =
-1;
while(left
!= right && right != pre)
{
if (chuizhi(jeo[left],
jeo[right], jeogia[i], jeogia[i + n])
&&
samedis(jeo[left], jeo[right], jeogia[i]))
{
pre = left;
left = (left - 1 + n) % n;
right = (right + 1) % n;
}else break;
}
if (left ==
right || right == pre)
{flag =
true; break;}
}
if (flag) break;
}
if (flag)
printf("YES\n");
else printf("NO\n");
}
return
0;
给你一个简单多边形，问你是否是轴对称的。
解题报告：
实际上就是加了“重心”这个强剪枝。
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
#define eps 1e-6
struct pint
{
}jeo[30000], jeogia[50000];
struct line{pint a,b;};
pint intersection(line u,line v){
}
pint barycenter(pint a,pint b,pint c){
}
double xmult(pint p1,pint p2,pint p0){
}
pint barycenter(int n,pint* p)
{
}
int n;
bool sameline(pint a, pint b, pint c)
{
}
bool chuizhi(pint a, pint b, pint c, pint d)
{
}
bool samedis(pint a, pint b, pint c)
{
}
int main()
{
}
喜欢
0
赠金笔