HDU 6127 Hard challenge

本文由 Ocrosoft 于 2017-08-16 14:39:38 发表

Hard challenge

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 963    Accepted Submission(s): 392

Problem Description
There are n points on the plane, and the ith points has a value vali, and its coordinate is (xi,yi). It is guaranteed that no two points have the same coordinate, and no two points makes the line which passes them also passes the origin point. For every two points, there is a segment connecting them, and the segment has a value which equals the product of the values of the two points. Now HazelFan want to draw a line throgh the origin point but not through any given points, and he define the score is the sum of the values of all segments that the line crosses. Please tell him the maximum score.
 

Input
The first line contains a positive integer T(1≤T≤5), denoting the number of test cases.
For each test case:
The first line contains a positive integer n(1≤n≤5×104).
The next n lines, the ith line contains three integers xi,yi,vali(|xi|,|yi|≤109,1≤vali≤104).
 

Output
For each test case:
A single line contains a nonnegative integer, denoting the answer.
 

Sample Input
	
2 2 1 1 1 1 -1 1 3 1 1 1 1 -1 10 -1 0 100
 

Sample Output
	
1 1100
 

Solution
2017 Multi-University Training Contest – Team 7
写的有点麻烦…

#define C11
#include <set>
#include <map>
#include <stack>
#include <string>
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#include <climits>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <functional>
#ifdef C11
#include <tuple>
#include <regex>
#include <random>
#include <complex>
#endif
using namespace std;
/** const var def */
const double eps = 1e-8;
const int maxn = 1e7 + 10;
const int MAXN = maxn * 4;
const int MOD = 1000000007;
const double PI = 4 * atan(1.0);
/** type def */
typedef long long LL;
typedef pair<int, int> Pii;
typedef pair<LL, LL> Pll;
typedef vector<int> Vi;
typedef pair<double, double> Vec2;
#ifdef C11
using Vec3 = tuple<double, double, double>;
using Tp3 = tuple<int, int, int>;
#endif
/** easy def */
#define _link(x) x&&x
#define ms(a) memset(a,0,sizeof(a))
#define msr(a) memset(a,-1,sizeof(a))
/* first, second, position */
#define _f first
#define _s second
#define _p(_tp,_pos) get<_pos>(_tp)
/* operator */
Pii operator +(const Pii &x, const Pii &y) { return Pii(x.first + y.first, x.second + y.second); }
Pii operator -(const Pii &x) { return Pii(-x.first, -x.second); }
Pii operator -(const Pii &x, const Pii &y) { return x + (-y); }
Pii operator +=(Pii &x, const Pii &y) { return x = x + y; }
Pii operator -=(Pii &x, const Pii &y) { return x = x - y; }
#pragma region input&output
template<class T>inline T read(T &num)
{
	char CH; bool F = false;
	for (CH = getchar(); CH<'0' || CH>'9'; F = CH == '-', CH = getchar());
	for (num = 0; CH >= '0'&&CH <= '9'; num = num * 10 + CH - '0', CH = getchar());
	F && (num = -num);
	return num;
}
template<class T>inline T read()
{
	T num;
	return read(num);
}
#ifdef C11
template<class T, class... Args>inline int read(T &t, Args &...args)
{
	read(t);
	read(args...);
	return t;
}
#endif
template<class T> inline void print(T p, char ed = '\n')
{
	int stk[70], tp = 0;
	if (p < 0) { putchar('-'); p = -p; }
	if (!p) { putchar('0'); if (ed != '\0')putchar(ed); return; }
	while (p) stk[++tp] = p % 10, p /= 10;
	while (tp) putchar(stk[tp--] + '0');
	if (ed != '\0')putchar(ed);
}
#ifdef C11
template<class T, class... Args>inline void print(T t, Args ...args)
{
	print(t, '\0');
	if (sizeof...(args))putchar(' ');
	else putchar('\n');
	print(args...);
}
#endif
#pragma endregion

#define _x(tp) _p(tp,0)
#define _y(tp) _p(tp,1)
#define _v(tp) _p(tp,2)
#define _r(tp) _p(tp,3)
int main()
{
	using Tp4 = tuple<int, int, int, double>;
	int N; read(N);
	while (N--)
	{
		int n; read(n);
		vector<Tp4> psu, psd;
		for (int i = 0; i < n; i++)
		{
			int x, y, v; double r;
			read(x, y, v);
			{
				if (x == 0)r = PI;
				else if (y == 0)r = PI;
				else if (x < 0 && y>0)r = PI - atan(-(double)y / (double)x);
				else if (x > 0 && y < 0)r = PI - atan(-(double)y / (double)x);
				else r = atan((double)y / (double)x);
			}
			if (y >= 0)psu.push_back(Tp4(x, y, v, r));
			else psd.push_back(Tp4(x, y, v, r));
		}
		sort(begin(psu), end(psu), [](const Tp4 &_Last,const Tp4 &_Pred) {
			double r1 = _r(_Last), r2 = _r(_Pred);
			int x1 = _x(_Last), x2 = _x(_Pred);
			if (x1 == 0)return x2 < 0;
			if (x2 == 0)return x1 > 0;
			return r1 < r2;
		});
		sort(begin(psd), end(psd), [](const Tp4 &_Last, const Tp4 &_Pred) {
			double r1 = _r(_Last), r2 = _r(_Pred);
			int x1 = _x(_Last), x2 = _x(_Pred);
			if (x1 == 0)return x2 > 0;
			if (x2 == 0)return x1 < 0;
			return r1 < r2;
		});
		auto itu = begin(psu), itd = begin(psd);
		LL sumU = 0, sumD = 0, ans = 0;
		for (auto each : psu)
			sumU += _v(each);
		for (auto each : psd)
			sumD += _v(each);
		for (; itu != end(psu) || itd != end(psd);)
		{
			if (itu == end(psu))goto UPEND;
			if (itd == end(psd))goto DOWNEND;
			double r1 = _r(*itu), r2 = _r(*itd);
			int x1 = _x(*itu), x2 = _x(*itd), y1 = _y(*itu), y2 = _y(*itd);
			if ((x1 == 0 && x2 < 0) || (x2 == 0 && x1 > 0) || r1 < r2)
			{
				DOWNEND:
				int v1 = _v(*itu);
				sumU -= v1;
				ans = max(ans, max((sumU + v1)*(sumD), sumU*(sumD + v1)));
				sumD += v1;
				itu++;
			}
			else
			{
				UPEND:
				int v2 = _v(*itd);
				sumD -= v2;
				ans = max(ans, max((sumU + v2)*(sumD), sumU*(sumD + v2)));
				sumU += v2;
				itd++;
			}
		}
		print(ans);
	}
	return 0;
}

 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 6127 Hard challenge

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址