首页 > 代码库 > POJ 1873 - The Fortified Forest 凸包 + 搜索 模板
POJ 1873 - The Fortified Forest 凸包 + 搜索 模板
通过这道题发现了原来写凸包的一些不注意之处和一些错误..有些错误很要命..
这题 N = 15
1 << 15 = 32768 直接枚举完全可行
卡在异常情况判断上很久,只有 顶点数 >= 2,即 n >= 3 时凸包才有意义
顶点数为 1 时,tmp = - 1 要做特殊判断。
总结了一下凸包模板
//template Convex Hull friend bool operator < (const point &p1, const point &p2){ return (p1.x < p2.x)||(p1.x == p2.x)&&(p1.y < p2.y); } void BBS(point p[], int n){ for (int i = 0; i < n; i++){ for (int j = 0; j < i; j++){ if (p[i] < p[j]) swap(p[i], p[j]); } } } void Convex_Hull(point p[], int n){ BBS(p, n); //先按横坐标升序排序,保证p[0]在凸包上 cur = 0; while (1){ int tmp = - 1; for (int i = 0; i < n; i++){ if (i != cur){ if (!(tmp + 1)||(((p[cur] >> p[i]) ^ (p[cur] >> p[tmp])) > 0)) tmp = i; } } if (tmp + 1){ //找到凸包上的点p[tmp] } if (!tmp||!(tmp + 1)) break; cur = tmp; } }
POJ1873.cpp
//POJ1873 //DFS + 凸包 //注意规避异常状况 //if (tmp + 1) // d += (p[cur] >> p[tmp]).norm(); //写代码不认真,出现了许多错误,务必注意 //AC 2016-10-14 #include "cstdio" #include "cstdlib" #include "cmath" #include "iostream" #define MAXN 20 double sqr(double x){ return x * x; } struct point{ int x, y, v, l; bool cut; point(){} point(int X, int Y): x(X), y(Y), cut(0){} friend point operator >> (const point &p1, const point &p2){ return point(p2.x - p1.x, p2.y - p1.y); } friend int operator ^ (const point &p1, const point &p2){ return p1.x * p2.y - p1.y * p2.x; } double norm(){ return sqrt(sqr(x) + sqr(y)); } friend bool operator < (const point &p1, const point &p2){ return (p1.x < p2.x)||(p1.x == p2.x)&&(p1.y < p2.y); } friend bool operator > (const point &p1, const point &p2){ return (p1.x > p2.x)||(p1.x == p2.x)&&(p1.y > p2.y); } }pt[MAXN], p[MAXN], ans[MAXN]; int m0, minval, n, val, len; double det; void GetPoints(point src[], point dest[], int n, int &m){ m = 0; for (int i = 0; i < n; i++){ if (!src[i].cut){ dest[m++] = src[i]; } } } template <class T> void swap(T &x, T &y){ T z = x; x = y; y = z; } void BBS(point p[], int n){ for (int i = 0; i < n; i++){ for (int j = 0; j < i; j++){ if (p[i] < p[j]) swap(p[i], p[j]); } } } void dfs(int x){ if (!(x + 1)){ int cur = 0, m, l = len; double d = 0, v = val; GetPoints(pt, p, n, m); BBS(p, m); for (int i = 0; i < m; i++){ v -= p[i].v; l -= p[i].l; } while (1){ int tmp = - 1; for (int i = 0; i < m; i++){ if (i != cur){ if (!(tmp + 1)||(((p[cur] >> p[i]) ^ (p[cur] >> p[tmp])) > 0)) tmp = i; } } if (tmp + 1) d += (p[cur] >> p[tmp]).norm(); if (!tmp||!(tmp + 1)) break; cur = tmp; } if (d > l) return; if ((v < minval)||(v == minval)&&(m < m0)){ minval = v, det = l - d, m0 = m; for (int i = 0; i < n; i++) ans[i] = pt[i]; } } else{ pt[x].cut = 0; dfs(x - 1); pt[x].cut = 1; dfs(x - 1); } } int main(){ int irr = 0; freopen("fin.c", "r", stdin); while(scanf("%d", &n), n){ val = len = 0, irr++, det = 0; m0 = 0x7f7f7f7f, minval = 0x7f7f7f7f; for (int i = 0; i < n; i++){ scanf("%d%d%d%d", &pt[i].x, &pt[i].y, &pt[i].v, &pt[i].l); val += pt[i].v, len += pt[i].l; } dfs(n - 1); if (irr > 1) puts(""); printf("Forest %d\n", irr); printf("Cut these trees:"); for (int i = 0; i < n; i++){ if (ans[i].cut) printf(" %d", i + 1); } printf("\nExtra wood: %.2f\n", det); } }
POJ 1873 - The Fortified Forest 凸包 + 搜索 模板
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。