多边形第一弹
程序员文章站
2024-03-16 19:46:46
...
多边形第一弹
做oj时发现这样一道题
题目描述
按顺时针或逆时针顺序输入一个简单多边形的每个顶点坐标,求这个多边形的面积。
在几何形状中,简单多边形是由直线,非相交的线段或“边”组成的扁平形状,其成对连接以形成封闭路径。(百度百科)
输入
第一行一个整数n,表示顶点数
接下来n行,每行2个整数x,y表示一个顶点坐标
输出
对于每组数据,输出一行,一个浮点数表示面积(保留7位小数)
对于这样一道题,我最初的想法是把n边形分割成具有n-2个共同顶点的三角形,分别计算其面积再相加。
#include<stdio.h>
#include<math.h>
double x[1000000],y[1000000];
int main()
{
int i,n;
double x0,y0,detx[2],dety[2],s=0;
scanf("%d",&n);
scanf("%lf%lf",&x0,&y0);
for(i=0;i<n-1;i++)
{
scanf("%lf%lf",&x[i],&y[i]);
}
for(i=0;i<n-2;i++)
{
detx[1]=x[i+1]-x0;
detx[0]=x[i]-x0;
dety[1]=y[i+1]-y0;
dety[0]=y[i]-y0;
s+=fabs(detx[0]*dety[1]-detx[1]*dety[0])/2;
}
printf("%.7f",s);
}
但oj苦苦过不去(各位大神有空帮我看看错哪了)。
于是求助隔壁班学霸,大佬甩给我这样一段代码:
1.给定一个n变形的n个顶点,再给任意一个顶点。
判断:这个顶点是否在多边形内?
骚操作:
射线法:过这个n变形外任意一点,做一条与这个点连接的射线,
计算与多边形相交的次数,
如果是偶数则在外侧,奇数在内侧。
更骚的操作来了:如何判断线段是否相交?
//功能:求点在有向直线左边还是右边 其中a的横坐标大!若横坐标相同则b的纵坐标大
//返回:0共线、1左边、-1右边
int left_right(point a,point b,double x,double y)
{
double t;
a.x -= x; b.x -= x;
a.y -= y; b.y -= y;
t = a.x*b.y-a.y*b.x;
return t==0 ? 0 : t>0?1:-1;
}
//功能:线段cd和直线ab是否相交 (一左一右就相交)
bool intersect1(point a,point b,point c,point d)
{
return left_right(a,b,c.x,c.y)^left_right(a,b,d.x,d.y)==-2;
}
//功能:判断线段cd和线段ab是否相交 (每条线段都被另一条直接截就ok)
bool intersect(point a,point b,point c,point d)
{
return intersect1(a,b,c,d) && intersect1(c,d,a,b);
}
2.给定一个n边形的n个顶点,让求n边形面积:
设 n 边形的点,按顺时针/逆时针的顺序依次是 (x1,y1)(x2,y2)......(xn,yn)
那么:s = (x1y2-x2y1)/2 + (x2y3-x3y2)/2 +......+ (xny1-x1yn)/2
这时的 s 是有向面积,还需要取绝对值。
for(i = 0;i<n;i++)
{
s += (a[i]*b[(i+1)%n]-a[(i+1)%n]*b[i])/2.0;//注意取模!!!
}
s = fabs(s);
(也不知道是什么原理)不过复制上就能ac了(又可以边喝快乐肥宅水边膜拜大佬了,(〃‘▽’〃)高兴!)
最终代码写出来是这样的
#include <stdio.h>
#include <math.h>
#include <string.h>
double a[100100],b[100100],ans=0;
int main()
{
int n,i; scanf("%d",&n);
for (i=0;i<n;i++)
{
scanf("%lf%lf",&a[i],&b[i]);
}
for(i = 0;i<n;i++)
{
ans += (a[i]*b[(i+1)%n]-a[(i+1)%n]*b[i])/2.0;//注意取模!!!
}
ans=fabs(ans);
printf("%.7f",ans);
return 0;
}
上一篇: 画布----规则的多边形(三角形,正方形....)
下一篇: MD5加密技术