【计算几何】【极角序】【前缀和】bzoj1132 [POI2008]Tro
2024-09-07 20:05:17
把点按纵坐标排序,依次枚举,把它作为原点,然后把之后的点极角排序,把叉积的公式稍微化简一下,处理个后缀和统计答案。
#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;
}
最新文章
- leetcode 217
- C#--网络流Stream、字节数组保存到字符串中
- DirectUI 收集资料
- myeclipse不编译解决方法
- regardless of how many processors are devoted to a parallelized execution of this program
- E3: PS4/PC 莎木3 众筹200万美元 9小时内达成
- Oracle创建用户及表空间 代码片段
- 在github上搭建博客(使用Jekyll)
- 【字符串匹配】UVALive 4670 模板题
- github上forck一个分支之后,如何和主分支同步
- endnote 使用方法
- Matlab 多项式拟合、稳健滤波等实用函数
- seq2seq-chatbot:200 行代码实现聊天机器人
- mysql 日期操作 增减天数、时间转换、时间戳(转)
- PHP系统级函数 get_headers() 包含有服务器响应一个 HTTP
- 1.gil全局解释器锁, 2. 死锁与递归锁 3. 信号量 4. Event事件 5. 线程queue
- centos 下 mysql+keepalived实现双主自由切换
- from * import *(ImportError: No module named *)为什么报错没有这个目录
- day3:vcp考试
- mysql中字符串类型char(n)和varchar(n)的区别
热门文章
- HttpClient测试类请求端和服务端即可能出现乱码的解决
- 桥接物理网卡,pipwork指定ip,外网连接,研究salt+docker
- windows远程桌面访问ubuntu12.04
- Round 0: Regionals 2010 :: NEERC Eastern Subregional
- eclipse怎样快速的给代码段添加try catch
- 【BZOJ1976】能量魔方 [最小割]
- bzoj2811 [Apio2012]Guard
- NOIP2005过河(青蛙过河)
- HDU3746(KMP求循环节)
- HDU1018 (斯特林公式)