QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#225181 | #7511. Planar Graph | Danilo21 | WA | 10ms | 4160kb | C++17 | 5.6kb | 2023-10-24 03:16:11 | 2023-10-24 03:16:11 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))
using namespace std;
struct Point{
ll x, y;
Point(ll x = 0, ll y = 0){ this->x = x; this->y = y; }
void Read(){ cin >> x >> y; }
Point operator+(const Point& a) const { return Point(x + a.x, y + a.y); }
Point operator-(const Point& a) const { return Point(x - a.x, y - a.y); }
ll operator*(const Point& a) const { return x*a.y - a.x*y; }
bool OnSegment(array<Point, 2> a) const {
ll x1 = min(a[0].x, a[1].x), x2 = max(a[0].x, a[1].x);
ll y1 = min(a[0].y, a[1].y), y2 = max(a[0].y, a[1].y);
return x > x1 && x < x2 && y > y1 && y < y2 && (*this - a[0]) * (a[1] - *this) == 0;
}
static int sig(ll x){ return x / max(abs(x), 1LL); }
static bool Intersect(array<Point, 2> a, array<Point, 2> b){
if (a[0].OnSegment(b) || a[1].OnSegment(b) || b[0].OnSegment(a) || b[1].OnSegment(a)) return 1;
int o1 = sig((a[1] - a[0]) * (b[0] - a[1])) * sig((a[1] - a[0]) * (b[1] - a[1]));
int o2 = sig((b[1] - b[0]) * (a[0] - b[1])) * sig((b[1] - b[0]) * (a[1] - b[1]));
return o1 == -1 && o2 == -1;
}
bool Inside(Point a, Point b, Point c) const {
if (OnSegment({a, b}) || OnSegment({b, c}) || OnSegment({c, a}))
return 1;
int o1 = sig((b - a) * (*this - b));
int o2 = sig((c - b) * (*this - c));
int o3 = sig((a - c) * (*this - a));
return o1 == o2 && o2 == o3;
}
};
const ll LINF = 4e18;
const int mxN = 110, INF = 2e9;
ll N, C, n, m, e, e1, comp[mxN*mxN];
Point p[mxN], q[mxN];
array<int, 2> E[mxN], E1[mxN*mxN];
array<int, 3> faces[mxN*mxN];
vector<int> g[mxN*mxN];
bool connected[mxN][mxN], vis[mxN*mxN], has[mxN*mxN];
void AddEdge(int u, int v){
g[u].pb(v);
g[v].pb(u);
}
void dfs(int s, int c){
comp[s] = c;
vis[s] = 1;
for (int u : g[s])
if (!vis[u]) dfs(u, c);
}
void Solve(){
cin >> n >> m >> e;
for (int i = 0; i < n; i++)
p[i].Read();
for (int i = 0; i < m; i++)
q[i].Read();
for (int i = 0; i < e; i++){
cin >> E[i][0] >> E[i][1];
E[i][0]--;
E[i][1]--;
connected[E[i][0]][E[i][1]] = 1;
connected[E[i][1]][E[i][0]] = 1;
}
for (int i = 0; i < n; i++){
for (int j = i+1; j < n; j++){
if (!connected[i][j]){
bool f = 1;
for (int k = 0; k < n; k++)
for (int l = k+1; l < n; l++)
if (connected[k][l] && Point::Intersect({p[i], p[j]}, {p[k], p[l]}))
f = 0;
if (f){
connected[i][j] = 1;
connected[j][i] = 1;
E1[e1++] = {i, j};
}
}
}
}
for (int i = 0; i < n; i++){
for (int j = i+1; j < n; j++){
if (connected[i][j]){
for (int k = j+1; k < n; k++){
if (connected[i][k] && connected[j][k]){
bool f = 1;
for (int l = 0; l < n; l++)
if (l^i && l^j && l^k && p[l].Inside(p[i], p[j], p[k]))
f = 0;
if (f) faces[N++] = {i, j, k};
}
}
}
}
}
for (int i = 0; i < e1; i++){
vector<int> idx;
for (int j = 0; j < N; j++){
int cnt = 0;
for (int k = 0; k < 3; k++)
if (faces[j][k] == E1[i][0] || faces[j][k] == E1[i][1])
cnt++;
if (cnt == 2) idx.pb(j);
}
if (idx.size() == 1) idx.pb(N);
AddEdge(idx[0], idx[1]);
}
for (int i = 0; i <= N; i++)
if (!vis[i]) dfs(i, C++);
for (int i = 0; i < m; i++){
int idx = N;
for (int j = 0; j < N; j++)
if (q[i].Inside(p[faces[j][0]], p[faces[j][1]], p[faces[j][2]]))
idx = j;
has[comp[idx]] = 1;
}
string ans = "";
for (int i = 0; i < e; i++){
vector<int> v;
for (int j = 0; j < N; j++){
int cnt = 0;
for (int k = 0; k < 3; k++)
if (faces[j][k] == E[i][0] || faces[j][k] == E[i][1])
cnt++;
if (cnt == 2) v.pb(comp[j]);
}
if (v.size() == 1) v.pb(comp[N]);
if (has[v[0]] || has[v[1]]) ans += '1';
else ans += '0';
}
cout << ans << en;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0); cerr.tie(0);
cout << setprecision(12) << fixed;
cerr << setprecision(12) << fixed;
cerr << "Started!" << endl;
int t = 1;
//cin >> t;
while (t--)
Solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3956kb
input:
4 1 3 -2 0 0 2 2 0 0 1 0 3 1 2 2 3 1 3
output:
111
result:
ok single line: '111'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4160kb
input:
13 35 13 13 12 16 -3 18 4 4 -7 23 -22 9 -23 23 11 12 -1 19 -5 15 -15 5 -15 -17 11 -17 -13 -20 19 11 -12 -10 14 -3 14 7 -4 -10 -23 -19 -12 -13 1 -22 10 -21 -1 18 -9 -8 1 13 22 12 -23 -9 -9 -12 -20 4 -3 -6 17 14 -10 10 13 -5 -2 -4 -12 13 22 -18 -21 19 5 12 -18 4 0 3 -17 5 -2 -2 0 8 0 -8 1 14 -18 3 -9 ...
output:
1111111111111
result:
ok single line: '1111111111111'
Test #3:
score: -100
Wrong Answer
time: 10ms
memory: 3896kb
input:
68 59 168 51 -57 -26 -51 -31 58 -45 -78 -46 -49 -53 14 76 -69 -64 32 58 -49 -1 12 -65 28 -15 -10 29 -53 25 -32 78 -41 24 -37 69 56 54 -10 3 36 -18 46 53 -30 41 -2 -30 13 -58 -37 -20 42 -48 -38 -42 22 64 0 9 -56 7 -11 -66 -23 19 -9 -26 -6 -61 -68 57 13 -13 50 -15 -11 -77 47 -77 57 78 51 -37 56 -75 24...
output:
001111111000111011100001010000001001010011010011101011001000100110011010001110010111011101001000000001010000101110100110000100100000101101011101100011000011111000000001
result:
wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '001111111000111011100001010000...1011101100011000011111000000001'