QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#673960 | #5276. K-Shaped Figures | IllusionaryDominance# | WA | 4ms | 3860kb | C++20 | 3.6kb | 2024-10-25 12:29:48 | 2024-10-25 12:29:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using pii = pair <int, int>;
inline int untitled(const pii &a) {
if (a.first < 0) {
// x < 0
return a.second < 0 ? 3 : 2;
}else {
return a.second < 0 ? 4 : 1;
}
}
inline bool cmp(const pii &a, const pii &b) {
int a_ = untitled(a), b_ = untitled(b);
if (a_ != b_) return a_ < b_;
// dya / dxa < dyb / dxb
return 1ll * a.second * b.first < 1ll * a.first * b.second;
}
const int MAX_N = 1000 + 5;
int N;
struct Segment{
int x1, y1, x2, y2;
Segment (int x1_ = 0, int y1_ = 0, int x2_ = 0, int y2_ = 0) : x1(x1_), y1(y1_), x2(x2_), y2(y2_) {}
inline bool operator < (const Segment &comp) const {
return cmp(pair(x2 - x1, y2 - y1), pair(comp.x2 - comp.x1, comp.y2 - comp.y1));
// return atan2(y2 - y1, x2 - x1) < atan2(comp.y2 - comp.y1, comp.x2 - comp.x1);
}
}seg[MAX_N];
pii node[MAX_N << 1];
inline bool check(const Segment &seg, int x0, int y0) {
int dx1 = x0 - seg.x1, dy1 = x0 - seg.y1;
int dx2 = seg.x2 - x0, dy2 = seg.y2 - y0;
// dy1 / dx1 = dy2 / dx2
return 1ll * dy1 * dx2 == 1ll * dx1 * dy2 && min(seg.x1, seg.x2) <= x0 && x0 <= max(seg.x1, seg.x2);
}
void solve() {
cin >> N;
for (int i = 1; i <= N; i ++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
node[i] = pair(x1, y1);
node[i + N] = pair(x2, y2);
seg[i] = Segment(x1, y1, x2, y2);
}
int ans = 0;
sort(node + 1, node + (N << 1) + 1);
int M = unique(node + 1, node + (N << 1) + 1) - node - 1;
for (int i = 1; i <= M; i ++) {
auto [x0, y0] = node[i];
vector <Segment> seg1;
vector <pii> seg2;
for (int j = 1; j <= N; j ++) {
if (seg[j].x1 == x0 && seg[j].y1 == y0) {
seg2.emplace_back(seg[j].x2 - seg[j].x1, seg[j].y2 - seg[j].y1);
}else if (seg[j].x2 == x0 && seg[j].y2 == y0) {
seg2.emplace_back(seg[j].x1 - seg[j].x2, seg[j].y1 - seg[j].y2);
}else if (check(seg[j], x0, y0)) {
seg1.push_back(seg[j]);
}
}
if (!(seg1.empty() || seg2.empty())) {
sort(seg1.begin(), seg1.end());
sort(seg2.begin(), seg2.end(), cmp);
auto ed = unique(seg2.begin(), seg2.end());
int n = ed - seg2.begin();
int i = 0, j = n - 1;
// fprintf(stderr, "n = %d\n", n);
// for (int i = 0; i < n; i ++) fprintf(stderr, "i = %d, dx = %d, dy = %d\n", i, seg2[i].first, seg2[i].second);
for (int k = 0; k < (int)seg1.size(); k ++) {
pii dir0 = pair(seg1[k].x2 - seg1[k].x1, seg1[k].y2 - seg1[k].y1);
pii dir1 = pair(seg1[k].x1 - seg1[k].x2, seg1[k].y1 - seg1[k].y2);
// fprintf(stderr, "k = %d, dir0 = (%d, %d), dir1 = (%d, %d)\n", k, dir0.first, dir0.second, dir1.first, dir1.second);
if (cmp(dir0, seg2[i])) i = 0;
if (cmp(seg2[j], dir1)) j = n - 1;
// i < dir0, j > dir1
while (i < n && cmp(seg2[i], dir0)) i ++;
i --; if (i < 0) i = n - 1;
while (j >= 0 && cmp(dir1, seg2[j])) j --;
j ++; if (j == n) j = 0;
int cnt0 = j <= i ? i - j + 1 : n - (j - i - 1), cnt1 = n - cnt0;
ans += (cnt0 * (cnt0 - 1) + cnt1 * (cnt1 - 1)) / 2;
}
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T --) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
input:
2 5 0 0 0 10 0 5 3 10 0 5 3 0 0 5 7 4 0 5 6 2 8 0 0 10 10 3 4 4 4 4 4 4 5 3 4 4 4 7 7 7 8 7 7 8 7 5 5 4 6 5 5 3 7
output:
6 2
result:
ok 2 number(s): "6 2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
10 3 -1 -1 0 -1 -1 -1 0 -1 -1 -1 1 1 3 1 -1 0 0 0 -1 1 1 0 1 1 -1 3 0 -1 1 1 -1 1 1 -1 1 1 -1 0 3 -1 0 0 1 -1 1 0 1 -1 1 -1 0 3 -1 1 1 1 1 0 0 -1 1 -1 -1 0 3 0 -1 0 0 1 -1 0 0 -1 -1 1 1 3 1 0 1 1 1 -1 1 0 0 -1 -1 0 3 1 1 0 -1 -1 0 0 1 0 1 -1 0 3 1 0 0 -1 1 0 1 -1 1 0 0 0 3 -1 -1 -1 0 1 -1 1 0 1 0 0 -1
output:
0 0 0 0 0 1 0 0 0 0
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
10 3 -3 2 -2 -1 3 -2 3 -4 3 4 2 5 3 0 -1 5 2 -4 -2 -1 5 1 4 5 -4 3 -3 5 -5 -5 -5 -4 -1 -3 -1 -5 -5 -1 3 -3 3 3 5 1 5 -4 5 2 -5 4 -5 3 4 2 -4 1 1 -5 1 4 -3 5 0 -3 3 3 -3 4 -2 -4 0 -5 -2 -5 2 -1 -4 3 4 -3 2 5 -3 -5 1 -4 5 2 0 5 3 -5 4 -4 -2 -5 -2 -5 2 2 4 -2 -5 3 2 -2 -4 0 2 4 0 -5 -4 -3 0 -4 3 2 5 1 ...
output:
0 0 0 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
10 3 17 -61 16 46 -77 4 48 29 -83 -85 64 -98 3 8 87 72 94 -48 72 -53 -78 -55 95 76 6 3 58 -2 -20 -59 57 20 -50 -7 24 -51 -87 38 3 -20 43 38 73 -13 -14 28 -67 -26 -100 -45 55 3 18 -23 85 -71 -31 -30 7 -54 68 -33 -78 -21 3 -71 36 -11 -53 -43 -2 27 -31 -24 -30 10 71 3 -4 -26 74 -83 12 -86 -73 -58 50 -8...
output:
0 0 0 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
10 3 -747205 986354 -977580 581513 -666338 455489 -636199 888600 -729203 319266 -350608 -89261 3 -449879 -106071 923151 488259 -503807 220920 -120026 346138 110986 442433 -18303 -189764 3 -620049 -67194 -918363 -449594 848473 640562 267788 -183468 846086 972796 -635121 98853 3 -762212 49768 -558584 ...
output:
0 0 0 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #6:
score: -100
Wrong Answer
time: 4ms
memory: 3860kb
input:
3333 3 1 0 0 0 1 1 -1 0 1 0 0 0 3 -1 0 1 0 1 0 1 -1 1 0 0 -1 3 -1 -1 0 -1 -1 -1 0 0 1 -1 1 1 3 1 1 0 -1 -1 0 0 0 0 0 1 0 3 -1 1 -1 0 -1 0 0 1 -1 -1 1 -1 3 0 -1 1 0 1 1 -1 -1 0 1 1 0 3 0 0 1 0 0 1 1 1 0 -1 0 0 3 1 1 -1 1 0 -1 -1 1 1 0 -1 0 3 1 1 -1 0 -1 1 1 0 0 0 -1 -1 3 -1 -1 -1 1 0 0 1 -1 -1 -1 1 1...
output:
0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 5th numbers differ - expected: '0', found: '1'