Gym - 101606L Lizard Lounge——LIS

Gym - 101606L Lizard Lounge——LIS

按照先极角后距离的顺序排序，然后对每一个序列求一遍LIS， 累加起来就是结果

#include #include #include #include #include #include using namespace std;const int maxn = 1e6 + 10;const int INF = 0x3f3f3f3f;const double eps = 1e-8;int dcmp(double x) { if (fabs(x) < eps) return 0; return x > 0 ? 1 : -1;}struct Node { int x, y, h; double angle; double dis; bool operator < (const Node &atr) const { if (dcmp(angle - atr.angle) != 0) return angle < atr.angle; return dis < atr.dis; }}node[maxn];vector v[maxn];int dp[maxn];int cx, cy, n;int main() { scanf("%d %d", &cx, &cy); scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d %d %d", &node[i].x, &node[i].y, &node[i].h); node[i].x -= cx, node[i].y -= cy; node[i].angle = atan2(node[i].y, node[i].x); node[i].dis = sqrt(1.0*node[i].x*node[i].x+1.0*node[i].y*node[i].y); } sort(node+1, node+1+n); int cnt = 0; for (int i = 1; i <= n; i++) v[i].clear(); v[++cnt].push_back(node[1].h); for (int i = 2; i <= n; i++) { if (dcmp(node[i].angle - node[i-1].angle) != 0) ++cnt; v[cnt].push_back(node[i].h); } int ans = 0; for (int i = 1; i <= cnt; i++) { int len = v[i].size(); for (int j = 0; j < len; j++) dp[j] = INF; for (int j = 0; j < len; j++) *lower_bound(dp, dp+len, v[i][j]) = v[i][j]; ans += lower_bound(dp, dp + len, INF) - dp; } printf("%d\n", ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。