关键词：
atan2 (-180----180]
http://acm.hdu.edu.cn/showproblem.php?pid=6127
1 #include <iostream> 2 #include <cmath> 3 #include <algorithm> 4 using namespace std; 5 #define ll long long 6 const int maxn = 5e4+10; 7 #define PI acos(-1.0) 8 int t, n, w; 9 ll sum; 10 double x, y; 11 struct Node 12 ll w; 13 double c; 14 T[maxn]; 15 bool cmp(Node a, Node b) 16 return a.c > b.c; 17 18 int main() 19 scanf("%d", &t); 20 while(t--) 21 sum = 0; 22 scanf("%d", &n); 23 for(int i = 0; i < n; ++i) 24 scanf("%lf%lf%lld", &x, &y, &T[i].w), T[i].c = atan2(y, x), sum += T[i].w; 25 26 sort(T, T+n, cmp); 27 int xx = 0; 28 ll sum2 = 0; 29 while(T[xx].c >= 0 && xx < n) sum2 += T[xx].w, xx++; 30 ll ma = 0; 31 int i = 0; 32 while(T[i].c >= 0) 33 if(PI - T[i].c > -T[xx].c && xx < n) 34 sum2 += T[xx].w, xx++; 35 ma = max(ma, sum2*(sum-sum2)); 36 else 37 sum2 -= T[i].w, i++; 38 ma = max(ma, sum2*(sum-sum2)); 39 40 41 printf("%lld\n", ma); 42 43 return 0; 44
只有不断学习才能进步！
极角排序常用方法(代码片段)
极角排序常用的四种方法：写在前面：存储点的结构体和函数 1structpoint//存储点23doublex,y;4;56doublecross(doublex1,doubley1,doublex2,doubley2) //计算叉积78return(x1*y2-x2*y1);91011doublecompare(pointa,pointb,pointc)//计算极角1213re 查看详情
wenbao与拓扑排序(代码片段)
@ dfs @ 小数据map存图 1intmark[maxn],map[maxn][maxn],aim[maxn],cot;2booldfs(intx)3mark[x]=-1;4for(inti=1;i<=n;i++)5if(map[x][i])6if(mark[i]<0)returnfalse;7if(!mark[i]& 查看详情
poj1696spaceant（极角排序）(代码片段)
题目：DescriptionThemostexcitingspacediscoveryoccurredattheendofthe20thcentury.In1999,scientiststraceddownanant-likecreatureintheplanetY1999andcalleditM11.Ithasonlyoneeyeontheleftsideofitsheadandjustthre 查看详情
poj1981最大点覆盖问题(极角排序）(代码片段)
CircleandPointsTimeLimit: 5000MS MemoryLimit: 30000KTotalSubmissions: 8346 Accepted: 2974CaseTimeLimit: 2000MSDescriptionYouaregivenNpointsinthexy-plane.Youhaveacirc 查看详情
codeforces196c.painttree(分治+极角排序)(代码片段)
C.PaintTreetimelimitpertest2secondsmemorylimitpertest256megabytesYouaregivenatreewith(n)vertexesand(n)pointsonaplane,nothreepointslieononestraightline.Yourtaskistopaintthegiventreeonaplane,usingth 查看详情
极角排序(代码片段)
极角排序在平面内取一个定点O，叫极点，引一条射线Ox，叫做极轴，再选定一个长度单位和角度的正方向（通常取逆时针方向）。对于平面内任何一点M，用ρ表示线段OM的长度（有时也用r表示）... 查看详情
codeforces598c.nearestvectors（极角排序）(代码片段)
题意：解法：极角排序之后,枚举相邻点取min即可.这题的atan2(y,x)会卡精度,传入的y和x开longdouble能过,开int就不行.code：#include<bits/stdc++.h>usingnamespacestd;#definePIpair<longdouble,int>constlongdoub 查看详情
poj1106极角排序(代码片段)
...的距离大于半径的点可以直接先排除掉。将剩余的点进行极角排序，然后用一个双端队列维护能被半圆覆盖的点，当队首和当前处理点的角度大于π\\piπ时，弹出队首元素。期间队列最大的size就是答案。需要注意的是... 查看详情
codeforcesgym101174bwithinarm'sreach极角排序(代码片段)
#include<stdio.h>#include<vector>#include<algorithm>usingnamespacestd;constintmaxn=1e5+10;structpointdoublex,y;voidin()scanf("%lf%lf",&x,&y);inlinepointf(pointa)constif(a 查看详情
poj1696极角排序求最长逆时针螺旋线(代码片段)
SpaceAntTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 4970 Accepted: 3100DescriptionThemostexcitingspacediscoveryoccurredattheendofthe20thcentury.In1999,scientis 查看详情
极角排序+求锐角三角形个数——uva12123(代码片段)
这个版本还不能处理三点共线的情况(处理起来其实比较麻烦)可以用atan2来排序(较为简单，但是精度误差大)，也可以用叉积排序(比较优秀)atan2#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath&g... 查看详情
极角排序——icpclatinamericanregionalcontests2019d(代码片段)
这题还是按角度进行极角排序简单点/*按亮度从大到小排序，从大的给小的连一条向量，极角排序后所有向量在两个象限内，那么可行，反之不可行*/#include<bits/stdc++.h>usingnamespacestd;#defineN1005typedefdoubledb;constdbeps=1e-8;constdb... 查看详情
极角排序+stl——hdu6731(代码片段)
碰到极角排序不能无脑就用双指针写，要思考是否有更加好的写法本题由于有三点共线，所以双指针扫描会有问题，由于只要求直角个数，所以我们可以直接用lower_bound二分去找这个就可以或者也可以用map重载point的=,<,>... 查看详情
凸包总结(代码片段)
...(a×b=0)则(a)与(b)共线若(a×b>0)则(a)在(b)的逆时针方向①极角排序选择一个点作为基础点，进行极角排序。可以通过比较叉积的方式进行极角排序，若叉积相同，则离基础 查看详情
「bzoj2391」cirno的忧郁(代码片段)
传送门设p[0]=(-10001,-10001)把所有点按p[0]极角排序，s[i][j]表示三角形p[0]p[i]p[j]内的总价值，若i到j极角增大则s为正，否则s为负。那么答案就是按顺序多边形每条边两个端点的s值之和的绝对值。如何求s枚举每个点x，建一颗平衡树... 查看详情
计算几何_凸包(代码片段)
极角排序求凸包 水平排序求凸包 极角排序structPointdoublex,y;Point()Point(double_x,double_y):x(_x),y(_y)Pointoperator+(constPoint&a)constreturnPoint(x+a.x,y+a.y);//叉积=0是指两向量平行（重合）Pointope 查看详情
wenbao与三分(代码片段)
--------------------------------------------------------------------https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3010 求 查看详情
wenbao与差分约束(代码片段)
推荐博客：http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html ----------------------------------------------------------- http://poj.org/problem?id=3169 1#inc 查看详情