把点按纵坐标排序,依次枚举,把它作为原点,然后把之后的点极角排序,把叉积的公式稍微化简一下,处理个后缀和统计答案。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 3002
typedef double db;
typedef long long ll;
struct Point{ll x,y;db jiao;}p[N],v[N];
int n;
ll sumx[N],sumy[N],ans;
bool cmp(const Point &a,const Point &b){return a.y<b.y;}
bool cmp2(const Point &a,const Point &b){return a.jiao<b.jiao;}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lld%lld",&p[i].x,&p[i].y);
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n-2;++i)
{
for(int j=i+1;j<=n;++j)
{
v[j].x=p[j].x-p[i].x;
v[j].y=p[j].y-p[i].y;
v[j].jiao=atan2((db)v[j].y,(db)v[j].x);
}
sort(v+i+1,v+n+1,cmp2);
for(int j=n;j>i;--j)
{
sumx[j]=sumx[j+1]+v[j].x;
sumy[j]=sumy[j+1]+v[j].y;
}
for(int j=i+1;j<n;++j)
ans+=(v[j].x*sumy[j+1]-v[j].y*sumx[j+1]);
}
printf("%lld",ans>>1);
if(ans&1) puts(".5");
else puts(".0");
return 0;
}

最新文章

  1. leetcode 217
  2. C#--网络流Stream、字节数组保存到字符串中
  3. DirectUI 收集资料
  4. myeclipse不编译解决方法
  5. regardless of how many processors are devoted to a parallelized execution of this program
  6. E3: PS4/PC 莎木3 众筹200万美元 9小时内达成
  7. Oracle创建用户及表空间 代码片段
  8. 在github上搭建博客(使用Jekyll)
  9. 【字符串匹配】UVALive 4670 模板题
  10. github上forck一个分支之后,如何和主分支同步
  11. endnote 使用方法
  12. Matlab 多项式拟合、稳健滤波等实用函数
  13. seq2seq-chatbot:200 行代码实现聊天机器人
  14. mysql 日期操作 增减天数、时间转换、时间戳(转)
  15. PHP系统级函数 get_headers() 包含有服务器响应一个 HTTP
  16. 1.gil全局解释器锁, 2. 死锁与递归锁 3. 信号量 4. Event事件 5. 线程queue
  17. centos 下 mysql+keepalived实现双主自由切换
  18. from * import *(ImportError: No module named *)为什么报错没有这个目录
  19. day3:vcp考试
  20. mysql中字符串类型char(n)和varchar(n)的区别

热门文章

  1. HttpClient测试类请求端和服务端即可能出现乱码的解决
  2. 桥接物理网卡,pipwork指定ip,外网连接,研究salt+docker
  3. windows远程桌面访问ubuntu12.04
  4. Round 0: Regionals 2010 :: NEERC Eastern Subregional
  5. eclipse怎样快速的给代码段添加try catch
  6. 【BZOJ1976】能量魔方 [最小割]
  7. bzoj2811 [Apio2012]Guard
  8. NOIP2005过河(青蛙过河)
  9. HDU3746(KMP求循环节)
  10. HDU1018 (斯特林公式)