mes noi return style clu ring min typedef logs
本来觉得挺简单的一道题却因为没考虑a>=0的情况而调试了一个上午,看来留给思考的时间应该更多一些,等各种特殊情况都想好之后再开始写代码
总之NOIP2016的题都做完啦
- #include < cstdio > #include < iostream > #include < cstring > #include < algorithm > using namespace std;
- typedef double db;
- typedef pair < db,
- db > P;
- int t,
- n,
- m,
- f[1 << 18],
- g[18][18];
- db a,
- b,
- eps = 1e-8;
- P p[18];
- int dbcmp(db a) {
- return a < -eps ? -1 : a > eps ? 1 : 0;
- }
- void pre() {
- int s;
- db x1,
- x2,
- y1,
- y2,
- x3,
- y3,
- a,
- b;
- for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {
- x1 = p[i].first,
- y1 = p[i].second,
- x2 = p[j].first,
- y2 = p[j].second;
- if (x1 == x2) continue;
- a = (x1 / x2 * y2 - y1) / (x1 * (x2 - x1)),
- b = y1 / x1 - a * x1;
- if (dbcmp(a) >= 0) continue;
- s = (1 << i) + (1 << j);
- for (int k = j + 1; k < n; k++) {
- x3 = p[k].first,
- y3 = p[k].second;
- if (dbcmp(a * x3 * x3 + b * x3 - y3) == 0) s += (1 << k);
- }
- g[i][j] = s;
- }
- }
- int main() {
- scanf("%d", &t);
- while (t--) {
- memset(f, 0x7f, sizeof(f));
- memset(g, 0, sizeof(g));
- scanf("%d%d", &n, &m);
- for (int i = 0; i < n; i++) scanf("%lf%lf", &a, &b),
- p[i] = P(a, b);
- sort(p, p + n);
- pre();
- f[0] = 0;
- for (int i = 0; i < (1 << n) - 1; i++) {
- int j = 0;
- while ((1 << j) & i) j++;
- for (int k = j + 1; k < n; k++) if (((1 << k) & i) == 0) f[i | g[j][k]] = min(f[i | g[j][k]], f[i] + 1);
- f[i | (1 << j)] = min(f[i | (1 << j)], f[i] + 1);
- }
- printf("%d\n", f[(1 << n) - 1]);
- }
- }
【计算几何+状压DP】愤怒的小鸟
mes noi return style clu ring min typedef logs
原文:http://www.cnblogs.com/algonote/p/7742649.html
来源: http://www.bubuko.com/infodetail-2368478.html