题目链接:http://uoj.ac/problem/265
题目大意:
太长了不想概括。。。
分析:
状压DP的模板题,把所有可能的抛物线用二进制表示,然后暴力枚举所有组合,详情见代码内注释
代码如下:
1 #pragma GCC optimize("Ofast") 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define INIT() std::ios::sync_with_stdio(false);std::cin.tie(0); 6 #define Rep(i,n) for (int i = 0; i < (n); ++i) 7 #define For(i,s,t) for (int i = (s); i <= (t); ++i) 8 #define rFor(i,t,s) for (int i = (t); i >= (s); --i) 9 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) 10 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) 11 12 #define pr(x) cout << #x << " = " << x << " " 13 #define prln(x) cout << #x << " = " << x << endl 14 15 #define LOWBIT(x) ((x)&(-x)) 16 17 #define ALL(x) x.begin(),x.end() 18 #define INS(x) inserter(x,x.begin()) 19 20 #define ms0(a) memset(a,0,sizeof(a)) 21 #define msI(a) memset(a,inf,sizeof(a)) 22 #define msM(a) memset(a,-1,sizeof(a)) 23 24 #define pii pair<int,int> 25 #define piii pair<pair<int,int>,int> 26 #define MP make_pair 27 #define PB push_back 28 #define ft first 29 #define sd second 30 31 template<typename T1, typename T2> 32 istream &operator>>(istream &in, pair<T1, T2> &p) { 33 in >> p.first >> p.second; 34 return in; 35 } 36 37 template<typename T> 38 istream &operator>>(istream &in, vector<T> &v) { 39 for (auto &x: v) 40 in >> x; 41 return in; 42 } 43 44 template<typename T1, typename T2> 45 ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) { 46 out << "[" << p.first << ", " << p.second << "]" << "\n"; 47 return out; 48 } 49 50 inline int gc(){ 51 static const int BUF = 1e7; 52 static char buf[BUF], *bg = buf + BUF, *ed = bg; 53 54 if(bg == ed) fread(bg = buf, 1, BUF, stdin); 55 return *bg++; 56 } 57 58 inline int ri(){ 59 int x = 0, f = 1, c = gc(); 60 for(; c<48||c>57; f = c=='-'?-1:f, c=gc()); 61 for(; c>47&&c<58; x = x*10 + c - 48, c=gc()); 62 return x*f; 63 } 64 65 typedef long long LL; 66 typedef unsigned long long uLL; 67 typedef pair< double, double > PDD; 68 typedef set< int > SI; 69 typedef vector< int > VI; 70 const double EPS = 1e-10; 71 const int inf = 1e9 + 9; 72 const LL mod = 1e9 + 7; 73 const int maxN = 1e5 + 7; 74 const LL ONE = 1; 75 76 int sgn(double x) { 77 if(fabs(x) < EPS) return 0; 78 return x > 0 ? 1 : -1; 79 } 80 81 struct Matrix{ 82 double m[3][3]; 83 84 Matrix(){} 85 Matrix(double x11, double x12, double x21, double x22) { 86 m[1][1] = x11; 87 m[1][2] = x12; 88 m[2][1] = x21; 89 m[2][2] = x22; 90 } 91 92 double det() { 93 return m[1][1] * m[2][2] - m[1][2] * m[2][1]; 94 } 95 }; 96 97 int T, n, m, ans; 98 PDD pig[20]; 99 // 用n位二进制数记录一条抛物线可能穿过的点的状态 100 // 比如抛物线过1号,5号,7号点,那么数值为 :000000000001010001 101 VI state; 102 SI si; 103 // f[i]为当前状态的最小步数 104 int f[1 << 18]; 105 106 int bitcount32(int bits) { 107 bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); 108 bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333); 109 bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f); 110 bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff); 111 return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff); 112 } 113 114 // 通过2个点算抛物线参数[a, b] 115 bool calcAB(PDD x, PDD y, PDD ¶) { 116 Matrix D = Matrix(x.ft * x.ft, x.ft, y.ft * y.ft, y.ft); 117 if(sgn(D.det()) == 0) return false; 118 Matrix D1 = Matrix(x.sd, x.ft, y.sd, y.ft); 119 Matrix D2 = Matrix(x.ft * x.ft, x.sd, y.ft * y.ft, y.sd); 120 121 para.ft = D1.det() / D.det(); 122 if(sgn(para.ft) >= 0) return false; 123 para.sd = D2.det() / D.det(); 124 return true; 125 } 126 127 // 验证点x是否符合抛物线 128 bool check(PDD x, PDD ¶) { 129 if(sgn(para.ft * x.ft * x.ft + para.sd * x.ft - x.sd) == 0) return true; 130 return false; 131 } 132 133 void solve() { 134 int ret = 0; 135 136 // 枚举所有点对 137 For(i, 1, n) { 138 For(j, i + 1, n) { 139 PDD p; 140 if(!calcAB(pig[i], pig[j], p)) continue; 141 // 看是否有其他点也经过这条抛物线 142 int st = 0; 143 st |= 1 << (i - 1); 144 st |= 1 << (j - 1); 145 For(k, 1, n) { 146 if(k == i || k == j) continue; 147 if(check(pig[k], p)) st |= 1 << (k - 1); 148 } 149 if(si.find(st) == si.end()) { 150 si.insert(st); 151 state.PB(st); 152 } 153 } 154 } 155 // 把只过一个点的抛物线也存一下 156 Rep(i, n) state.PB(1 << i); 157 // 把所有抛物线都得到后,问题就变成在这些抛物线中最少能选取几条,进行或运算后二进制1~n位全为1 158 msI(f); 159 f[0] = 0; 160 int len = state.size(); 161 162 Rep(i, 1 << n) { 163 // 当枚举到f[i]时,f[i]已经是最优解了 164 Rep(j, len) { 165 f[i | state[j]] = min(f[i | state[j]], f[i] + 1); 166 } 167 } 168 169 ans = f[(1 << n) - 1]; 170 } 171 172 int main(){ 173 INIT(); 174 cin >> T; 175 while(T--) { 176 state.clear(); 177 si.clear(); 178 cin >> n >> m; 179 For(i, 1, n) cin >> pig[i]; 180 solve(); 181 182 cout << ans << endl; 183 } 184 185 return 0; 186 }