辽宁城乡建设集团官方网站,怎样免费建设个人网站,wordpress 文章id 链接,中国铁建门户登录Hard challenge
思路
通过极角排序#xff0c;这里通过修改后#xff0c;所有点的角度在[0,2π)[0, 2 \pi)[0,2π)之间#xff0c;
然后O(n)O(n)O(n)扫一趟#xff0c;对当前在的级角加上π\piπ就是我们要找的角度了#xff0c;这里通过二分来实现查找。
接下来就只要…Hard challenge
思路
通过极角排序这里通过修改后所有点的角度在[0,2π)[0, 2 \pi)[0,2π)之间
然后O(n)O(n)O(n)扫一趟对当前在的级角加上π\piπ就是我们要找的角度了这里通过二分来实现查找。
接下来就只要通过前缀和思想来得到这个最大值了。
假设我们当前所在的是iii因为角度在[0,2π)[0, 2\pi)[0,2π)所以我们查找的jjj的下标可能会有两种情况
1j i这个时候有连续的一段区间[l, j]是属于一个集合。
2j i这个时候有连续的一段区间[j 1, i - 1]是属于一个集合
所以我们只要特判这两种情况即可。
代码
/*Author : lifehappy
*/
#include cstdio
#include cmath
#include cstring
#include algorithm
#include vector
#include iostreamusing namespace std;typedef long long ll;const double pi acos(-1.0);
const double eps 1e-5;
const double inf 1e100;int Sgn(double x) {return x -eps ? -1 : x eps;
}struct Vector {double x, y, angle;int w;bool operator (Vector a) const {return x a.x;}void print() {printf(%f %f\n, x, y);}void read() {scanf(%lf %lf, x, y);}Vector(double _x 0, double _y 0) : x(_x), y(_y) {}double mod() {return sqrt(x * x y * y);}double mod2() {return x * x y * y;}Vector operator (const Vector a) {return Vector(x a.x, y a.y);}Vector operator - (const Vector a) {return Vector(x - a.x, y - a.y);}double operator * (const Vector a) {return x * a.x y * a.y;}double operator ^ (const Vector a) {return x * a.y - y * a.x;}Vector Rotate(double angle) {return Vector(x * cos(angle) - y * sin(angle), x * sin(angle) y * cos(angle));}Vector operator (const double a) {return Vector(x * a, y * a);}Vector operator (const double a) {return Vector(x / a, y / a);}
};typedef Vector Point;double Dis_pp(Point a, Point b) {return sqrt((a - b) * (a - b));
}double Angle(Vector a, Vector b) {double ans atan2(a ^ b, a * b);if(ans 0) ans 2 * pi;return ans;// return atan2(a ^ b, a * b);
}double To_lefttest(Point a, Point b, Point c) {return (b - a) ^(c - a);
}int Toleft_test(Point a, Point b, Point c) {return Sgn((b - a) ^ (c - a));
}struct Line {Point st, ed;Line(Point _st Point(0, 0), Point _ed Point(0, 0)) : st(_st), ed(_ed) {}bool operator (const Line t) {return st.x t.st.x;}void read() {scanf(%lf %lf %lf %lf, st.x, st.y, ed.x, ed.y);}
};bool Parallel(Line a, Line b) {return Sgn((a.st - a.ed) ^ (b.st - b.ed)) 0;
}bool Is_cross(Line a, Line b) {return Toleft_test(a.st, a.ed, b.st) * Toleft_test(a.st, a.ed, b.ed) 0 Toleft_test(b.st, b.ed, a.st) * Toleft_test(b.st, b.ed, a.ed) 0;
}Point Cross_point(Line a, Line b) {if(!Is_cross(a, b)) {return Point(inf, inf);}else {double a1 fabs(To_lefttest(a.st, a.ed, b.st)), a2 fabs(To_lefttest(a.st, a.ed, b.ed));return ((b.st a2) (b.ed a1)) (a1 a2);}
}Point Shadow(Line a, Point b) {Point dir a.ed - a.st;return a.st (dir (((b - a.st) * dir) / dir.mod2()));
}Point Reflect(Line a, Point b) {return (Shadow(a, b) 2) - b;
}bool inmid(double a, double b, double x) {if(a b) swap(a, b);return Sgn(x - a) 0 Sgn(b - x) 0;
}bool Point_in_line(Line a, Point b) {if(Toleft_test(a.st, a.ed, b) ! 0) return false;return inmid(a.st.x, a.ed.x, b.x) inmid(a.st.y, a.ed.y, b.y);
}double Dis_lp(Line a, Point b) {Point h Shadow(a, b);if(Point_in_line(a, h)) {return Dis_pp(h, b);}return min(Dis_pp(a.st, b), Dis_pp(a.ed, b));
}double Dis_ll(Line a, Line b) {if(Is_cross(a, b)) return 0;return min({Dis_lp(a, b.st), Dis_lp(a, b.ed), Dis_lp(b, a.st), Dis_lp(b, a.ed)});
}double Area(vectorPoint p) {int n p.size();double ans 0;for(int i 0; i n; i) {ans p[i] ^ p[(i 1) % n];}return 0.5 * ans;
}bool cmp(Point a, Point b) {return a.angle b.angle;
}const int N 5e4 10;Point a[N];ll value[N];int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int T;scanf(%d, T);while(T--) {int n;scanf(%d, n);for(int i 1; i n; i) {a[i].read();scanf(%d, a[i].w);a[i].angle Angle(Point(1, 0), Point(a[i].x, a[i].y));}ll sum 0, ans 0;sort(a 1, a 1 n, cmp);for(int i 1; i n; i) {value[i] value[i - 1] a[i].w;sum a[i].w;}for(int i 1; i n; i) {double now a[i].angle, need now pi;if(need 2 * pi) need - 2 * pi;int l 1, r n;while(l r) {int mid l r 1 1;if(a[mid].angle need) r mid - 1;else l mid;}if(a[l].angle need) l;l--;if(l i) {ans max(ans, (sum - value[l] value[i - 1]) * (value[l] - value[i - 1]));}else {ans max(ans, (sum - value[i - 1] value[l]) * (value[i - 1] - value[l]));}}printf(%lld\n, ans);}return 0;
}
