2022杭电多校五_1004

杭电多校五

1004-The Surveying

1004 The Surveying (hdu.edu.cn)

prob.: 有n个观测点，m个建筑（以矩形四点的格式给出），问最少取多少个观测点使得m个建筑的四角以及每个选中的观测点都至少被一个观测点观测到

ideas： 刚开始想法是直接套bitset暴力枚举每个观测点能看到的建筑点以及观测点，在每个状态里判是否合法

确实不太写代码但觉得这题连个double都没有非常可做（确实算可做的题了，比起某icpcf的大分讨几何（？

然后喜提T，嘻嘻

2019-hdu-multi-（2019杭电多校第二场数据与标程）.zip

zip 0星 超过10%的资源 25.26MB

下载

赛后和队友交流的时候，队友们提了一百种优化，shift，关于赛中为什么不交流一哈子我真的会后悔

刚开始的朴素复杂度为$T\times 2^n\times n\times (\frac{4\times m}{32}+n^2)$

然后优化成了 $T\times 2^n\times n\times (\frac{4\times m}{32})$ 还是T

预处理+lowbit枚举状态转移再优化一个n变成$T\times 2^n\times \frac{4\times m}{32}$

注意bitset的使用

code：

#include 

using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

const double eps = 1e-9;
const double PI = acos(-1.0);
const double dinf = 1e99;
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct Line;

struct Point {
    ll x, y;

    Point() { x = y = 0; }

    Point(const Line &a);

    Point(const double &a, const double &b) : x(a), y(b) {}

    Point operator+(const Point &a) const {
        return {x + a.x, y + a.y};
    }

    Point operator-(const Point &a) const {
        return {x - a.x, y - a.y};
    }

    Point operator*(const double &a) const {
        return {x * a, y * a};
    }

    Point operator/(const double &d) const {
        return {x / d, y / d};
    }

    bool operator==(const Point &a) const {
        return abs(x - a.x) + abs(y - a.y) < eps;
    }

};


struct Line {
    Point s, t;

    Line() {}

    Line(const Point &a, const Point &b) : s(a), t(b) {}

};

Point::Point(const Line &a) { *this = a.t - a.s; }

istream &operator>>(istream &in, Point &a) {
    in >> a.x >> a.y;
    return in;
}

ostream &operator<<(ostream &out, Point &a) {
    out << fixed << setprecision(10) << a.x << ' ' << a.y;
    return out;
}

//鐐圭Н
ll dot(const Point &a, const Point &b) { return a.x * b.x + a.y * b.y; }

//鍙夌Н
ll det(const Point &a, const Point &b) { return a.x * b.y - a.y * b.x; }

//姝ｈ礋鍒ゆ柇
int sgn(const double &x) { return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1); }

//鐐筽鍦ㄧ嚎娈祍eg涓婏紝<=0鍒欏寘鍚鐐?
bool sp_on(const Line &seg, const Point &p) {
    Point a = seg.s, b = seg.t;
    return !sgn(det(p - a, b - a)) && sgn(dot(p - a, p - b)) <= 0;
}

//涓ょ洿绾跨殑鐒︾偣
Point ll_intersection(const Line &a, const Line &b) {
    double s1 = det(Point(a), b.s - a.s), s2 = det(Point(a), b.t - a.s);
    if (sgn(s1) == 0 && sgn(s2) == 0) return a.s;
    return (b.s * s2 - b.t * s1) / (s2 - s1);
}

//涓ょ嚎娈典氦鐐筽锛岃繑鍥?涓烘棤浜ょ偣锛?涓轰氦鐐逛负绔偣锛?涓虹浉浜?
int ss_cross(const Line &a, const Line &b, Point &p) {
    int d1 = sgn(det(a.t - a.s, b.s - a.s));
    int d2 = sgn(det(a.t - a.s, b.t - a.s));
    int d3 = sgn(det(b.t - b.s, a.s - b.s));
    int d4 = sgn(det(b.t - b.s, a.t - b.s));
    if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) {
        p = ll_intersection(a, b);
        return 1;
    }
    if (!d1 && sp_on(a, b.s)) {
        p = b.s;
        return 2;
    }
    if (!d2 && sp_on(a, b.t)) {
        p = b.t;
        return 2;
    }
    if (!d3 && sp_on(b, a.s)) {
        p = a.s;
        return 2;
    }
    if (!d4 && sp_on(b, a.t)) {
        p = a.t;
        return 2;
    }
    return 0;
}

------

vector<Point> stations;
vector<Point> buildingPoints;
vector<Line> buildingLines;

bitset<410> s[50];
bitset<410> bit[(1 << 20) + 20];
int rrr[(1 << 20) + 20];
int cnt[(1 << 20) + 20];
int canse[50];

void init() {
    stations.clear();
    buildingLines.clear();
    buildingPoints.clear();
    for (int i = 0; i < (1 << 20); ++i) {
        bit[i].reset();
        rrr[i] = 0;
    }
    for (int i = 0; i < 50; ++i) {
        s[i].reset();
        canse[i] = 0;
    }
}

signed main() {

//    Line linnne1 = {{1, 0}, {2, 0}};
//    Line linnne2 = {{-1,0}, {3, 0}};
//    Point poooint;
//    cerr << ss_cross(linnne1, linnne2, poooint);

//    freopen("1004.in", "r", stdin);
//    freopen("out.out", "w", stdout);

    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    for (int st = 1; st < (1 << 20); ++st) {
        for (int i = 0; i < 20; ++i) {
            if ((st >> i) & 1) cnt[st]++;
        }
    }

    int _;
    cin >> _;
    while (_--) {
        int n, m;
        cin >> n >> m;

        init();

        for (int i = 0; i < n; ++i) {
            ll x, y;
            cin >> x >> y;
            stations.push_back({x, y});
        }
        for (int i = 0; i < m; ++i) {
            Point p1, p2, p3, p4;
            cin >> p1.x >> p1.y;
            cin >> p2.x >> p2.y;
            cin >> p3.x >> p3.y;
            cin >> p4.x >> p4.y;
            buildingPoints.push_back(p1);
            buildingPoints.push_back(p2);
            buildingPoints.push_back(p3);
            buildingPoints.push_back(p4);
            buildingLines.push_back({p1, p2});
            buildingLines.push_back({p2, p3});
            buildingLines.push_back({p3, p4});
            buildingLines.push_back({p4, p1});
        }

        for (int i = 0; i < n; ++i) {
            Point p = stations[i];
            for (int j = i + 1; j < n; ++j) {
                Line tmpLine = {p, stations[j]};
                bool flag = 0;
                for (int k = 0; k < buildingLines.size(); ++k) {
                    Line Line2 = buildingLines[k];
                    Point tmppoint;
                    if (ss_cross(tmpLine, Line2, tmppoint) == 1) {
                        flag = 1;
                        break;
                    }
                }
                if (!flag) {
                    canse[i] |= (1 << j);
                    canse[j] |= (1 << i);
                }
            }
            for (int j = 0; j < buildingPoints.size(); ++j) {
                Line tmpLine = {p, buildingPoints[j]};
                bool flag = 0;
                for (int k = 0; k < buildingLines.size(); ++k) {
                    Line Line2 = buildingLines[k];
                    Point tmppoint;
                    if (ss_cross(tmpLine, Line2, tmppoint) == 1) {
                        flag = 1;
                        break;
                    }
                }
                if (!flag) {
                    s[i].set(j);
                }
            }
        }

        for (int st = 0; st < (1 << n); ++st) {
            for (int i = 0; i < n; ++i) {
                if ((st >> i) & 1) {
                    bit[(1 << i)] = s[i];
                    rrr[(1 << i)] = canse[i];
                }
            }
        }


        int ans = 0x3f3f3f3f;
        for (int st = 0; st < (1 << n); ++st) {
            bit[st] = bit[st - (st & -st)] | bit[(st & -st)];
            rrr[st] = rrr[st - (st & -st)] | rrr[(st & -st)];
            if (((rrr[st] & st) == st) && bit[st].count() == buildingPoints.size()) {
                ans = min(ans, cnt[st]);
            }
        }

        if (ans == 0x3f3f3f3f) cout << "No Solution!" << endl;
        else cout << ans << endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247