QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#227072 | #6806. Landlord | jzh# | RE | 1ms | 4044kb | C++20 | 3.0kb | 2023-10-26 20:55:56 | 2023-10-26 20:55:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Point {
ll x, y;
Point() = default;
Point(ll x_, ll y_): x(x_), y(y_) {}
friend Point operator-(Point A, Point B) {return Point(A.x-B.x, A.y-B.y);}
friend ll operator*(Point A, Point B) {return A.x*B.x + A.y*B.y;}
bool operator==(Point X) {return x == X.x && y == X.y;}
bool operator<(Point X) {return x != X.x ? x < X.x : y < X.y;}
void input() {
scanf("%lld%lld", &x, &y);
x*=2;
y*=2;
}
};
ll mul(Point v1, Point v2) {
return v1.x*v2.y - v1.y*v2.x;
}
ll sig(ll x) {
if (x == 0) return 0;
else if (x > 0) return 1;
else return -1;
}
bool pt_on_seg(Point X, Point A, Point B) {
if (mul(X-A, X-B) != 0) return false;
if ((X-A)*(X-B) > 0) return false;
return true;
}
bool seg_intersect(Point a1, Point a2, Point a3, Point a4) {
if (
pt_on_seg(a1, a3, a4) || pt_on_seg(a2, a3, a4) ||
pt_on_seg(a3, a1, a2) || pt_on_seg(a4, a1, a2)
) return true;
ll f1, f2;
f1 = sig(mul(a1-a2, a1-a3)) * sig(mul(a1-a2, a1-a4));
f2 = sig(mul(a3-a4, a3-a1)) * sig(mul(a3-a4, a3-a2));
return f1 < 0 && f2 < 0;
}
bool check_conn(Point A, Point B, Point LD, Point RU) {
if (A == B) return true;
if (seg_intersect(A, B, Point(LD.x, LD.y), Point(RU.x, LD.y))) return false;
if (seg_intersect(A, B, Point(RU.x, LD.y), Point(RU.x, RU.y))) return false;
if (seg_intersect(A, B, Point(RU.x, RU.y), Point(LD.x, RU.y))) return false;
if (seg_intersect(A, B, Point(LD.x, RU.y), Point(LD.x, LD.y))) return false;
return true;
}
vector<Point> a;
bool vis[100];
bool graph[100][100];
int n;
void dfs(int x) {
vis[x] = 1;
for (int i=0; i<n; i++) if (!vis[i] && graph[x][i]) {
dfs(i);
}
}
void solve()
{
vector<Point> p(4);
Point tmp;
for (int i=0; i<4; i++) p[i].input();
vector<Point> vec;
for (int i=0; i<=2; i+=2) {
Point &A = p[i];
Point &B = p[i+1];
vec.emplace_back(A.x, A.y);
vec.emplace_back(A.x, B.y);
vec.emplace_back(B.x, A.y);
vec.emplace_back(B.x, B.y);
}
n = 0;
for (auto A: vec) {
for (int dx=-1; dx<=1; dx+=2)
for (int dy=-1; dy<=1; dy+=2) {
tmp = Point(A.x+dx, A.y+dy);
//a[++n] = tmp;
a.push_back(tmp);
}
}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()));
n = a.size();
for (int i=0; i<n; i++) for (int j=0; j<n; j++) {
vis[i] = 0;
graph[i][j] = (
check_conn(a[i], a[j], p[0], p[1]) &&
check_conn(a[i], a[j], p[2], p[3])
);
}
int ans = 0;
for (int i=0; i<n; i++) if (!vis[i]) {
ans++;
dfs(i);
}
printf("%d\n", ans);
}
int main()
{
int ttt;
scanf("%d", &ttt);
while (ttt--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4044kb
input:
3 0 0 1 1 2 2 3 4 1 0 3 2 0 1 2 3 0 0 1 1 0 0 1 1
output:
3 4 2
result:
ok 3 lines
Test #2:
score: -100
Runtime Error
input:
10000 399413444 601729739 838979329 605646850 176742602 192902430 399413444 601729739 19226489 2915752 27806715 977516728 4075670 1872865 19226489 925008461 45547871 393001695 58201503 713825285 18241876 197851829 45547871 713825285 237513514 504913958 868997719 543598899 134432693 110279295 2375135...