多边形面积_ssl1213_计算几何

Description

　　中学生杰利陶醉于数学研究．他思考的问题对于专家而言可能太多简单，但作为一个15岁的业余爱好者，他做得非常棒．他太热衷思考数学问题，以至于轻易就学会了试用数学方法来解决碰到的问题．一天，他看到桌上的一张纸．他四岁的妹妹玛利在上央画了一些线．那些线恰好构成了一个凹多边形，如下图：
多边形面积_ssl1213_计算几何
　　＂棒极了＂，他想，＂这些多边形看起来是规则的．我曾经学过怎样计算三角形、矩形和圆形的面积。我一定能找到计算这些图形的方法。＂他确实做到了。首先，他标记多边形顶点的坐标。如图二所示。随后，他毫不费力的求得结果0.75。
多边形面积_ssl1213_计算几何
　　当然，他不会满足解决这样简单的问题。“嗯，如果纸上面是任意一个多边形，我们应该怎样计算它的面积呢？”他问自己。可他一直都没有找到计算多边形面积的通用方法。他清楚地明白以他的能力无法找到总是的答案。所以他向你请教。他会很感谢你的好心帮助。

Input

第一行是一个整数n，代表图形的顶点数（１＜＝n＜＝１０００）．
接下来的n行，每行一对实数，代表顶点坐标(xi,yi)。每个样例的图形由第一个顶点连接第二个顶点，第二个顶点连接第三个顶点……最后第n个顶点连接第一个顶点形成封闭多边形。

Output

输出图形面积或字符串”Impossible”
如果图形是一个多边形，计算他的面积（精确到小数点后两位）。如果输入的顶点不能构成多边形（也就是说，一条边和另一条边不相连的边相交，例如，四条线段的图形，第一条线段和第三条线段相交），就输出”Impossible”。指出图形不可能是多边形。如果顶点的数量不足以构成一个封闭的多边形，也输出”Impossible”

Analysis

n只有1000，枚举不同边判断相交，叉积算面积

判断两线段是否相交：

线段a的两端点一定处在线段b的两侧(叉积相乘为负数)
线段b的两端点一定处在线段a的两侧

数据坑会有0 ~~(零个端点是毛多边形啊！！！！)~~
再一次show出c++党的优越性

Code

#include <stdio.h>
using namespace std;
struct point{double x,y;}t[1001];
double cros(point a,point b,point c)
{
return ((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x))*0.5;
}
bool banana(point a,point b,point c,point d)
{
return (cros(b,c,a)*cros(b,d,a)<0&&cros(d,a,c)*cros(d,b,c)<0);
}
int main()
{
int n;
double ans=0;
scanf("%d",&n);
if (n<=2)
    {
printf("Impossible\n");
return 0;
    }
for (int i=1;i<=n;i++)
scanf("%lf%lf",&t[i].x,&t[i].y);
for (int i=2;i<=n;i++)
for (int j=1;j<n;j++)
if ((i!=j)&&(i!=j+1)&&banana(t[i-1],t[i],t[j],t[j+1]))
            {
printf("Impossible\n");
return 0;
            }
for (int i=3;i<=n;i++)
        ans+=cros(t[i],t[i-1],t[1]);
if (ans<0)
        ans=-ans;
printf("%.2f\n",ans);
return 0;
}

秒客网