QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#671562 | #5426. Drain the Water Tank | puremg | WA | 0ms | 3804kb | C++14 | 5.8kb | 2024-10-24 13:23:37 | 2024-10-24 13:23:38 |
Judging History
answer
//Author: Puremg
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC optimize(3,"Ofast")
#include <bits/stdc++.h>
#define deg(a) cout<<#a<<'='<<a<<"\n"
#define int long long
#define all(a) a.begin(), a.end()
// #define db double
#define ldb long double
#define db ldb
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e7+10;
const db eps = 1e-9;
const db pi = acos(-1);
mt19937_64 rng(random_device{}());
int sgn(ldb x) {
if (fabs(x) < eps) return 0;
else if (x > 0) return 1;
else return -1;
}
template<typename T> struct Point
{
T x,y;
Point(){}
Point(T x, T y):x(x),y(y){}
bool operator==(const Point &a) const {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}
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 {return {-x,-y};}
Point operator*(const T k) const {return {k*x,k*y};}
Point operator/(const T k) const {return {x/k,y/k};}
T operator*(const Point &a) const {return x*a.x+y*a.y;} //Dot
T operator^(const Point &a) const {return x*a.y-y*a.x;} //Cross
bool operator<(const Point &a) const {if (abs(x-a.x)<=eps) return y<a.y-eps; return x<a.x-eps;}
bool is_par(const Point &a) const {return abs((*this)^a)<=eps;}
bool is_ver(const Point &a) const {return abs((*this)*a)<=eps;}
int toleft(const Point &a) const {auto t=(*this)^a; return (t>eps)-(t<-eps);}
T len2() const {return (*this)*(*this);}
T dis2(const Point &a) const {return (a-(*this)).len2();}
double len() const {return sqrt(len2());}
double dis(const Point &a) const {return (a-(*this)).len();}
double ang(const Point &a) const {return acos(((*this)*a)/(this->len()*a.len()));}
Point rot(const double rad) const {return {x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};}
int sign() const {
if (y < 0 or (x > 0 and y == 0)) return 0;
return 1;
}
};
template<typename T> struct Line
{
Point<T> p,v; //p+tv
// Line(Point<T> p, Point<T> v) : p(p), v(v){}
bool operator==(const Line &a) const {return (v.is_par(a.v) && v.is_par(p-a.p));}
bool is_par(const Line &a) const {return (v.is_par(a.v) && !v.is_par(p-a.p));}
bool is_ver(const Line &a) const {return v.is_ver(a.v);}
bool is_on(const Point<T> &a) const {return v.is_par(a-p);}
int toleft(const Point<T> &a) const {return v.toleft(a-p);} // 直线和点的位置关系
Point<T> inter(const Line &a) const {return p+v*((a.v^(p-a.p))/(v^a.v));} // 两条直线交点
double dis(const Point<T> &a) const {return abs(v^(a-p))/v.len();}
Point<T> proj(const Point<T> &a) const {return p+v*((v*(a-p))/(v*v));} // 点在这条直线的投影
};
using P = Point<ldb>;
using L = Line<ldb>;
bool is_point_on_segment(P a, P b, P p) {
P ap = p - a, bp = p - b;
if (sgn(ap^bp)==0 and (ap*bp)<=0) return 1;
return 0;
}
int is_point_in_polygon(P p, vector<P> &poly, int n) {
int wn = 0;
for (int i = 1; i <= n; i ++) {
int left_test = (poly[i%n+1]-poly[i]).toleft(p-poly[i]);
int d1 = sgn(poly[i].y - p.y), d2 = sgn(poly[i%n+1].y - p.y);
if (left_test > 0 and d1 <= 0 and d2 > 0) wn ++;
if (left_test < 0 and d1 > 0 and d2 <= 0) wn --;
}
return wn;
}
void solve() {
int n;
cin >> n;
vector<P> a(n + 10);
for (int i = 1; i <= n; i ++) {
int x, y;
cin >> x >> y;
a[i].x = 1. * x;
a[i].y = 1. * y;
}
int ans = 0;
vector<int> ji(n + 10);
for (int i = 1; i <= n; i ++) {
int pre = i - 1;
if (pre == 0) pre = n;
int nxt = i + 1;
if (nxt == n + 1) nxt = 1;
if (sgn(a[pre].y - a[i].y) < 0 or sgn(a[nxt].y - a[i].y) < 0) continue;
if (sgn(a[pre].y - a[i].y) == 0 or sgn(a[nxt].y - a[i].y) == 0) {
while (sgn(a[nxt].y - a[i].y) == 0 and nxt != i) {
nxt ++;
if (nxt == n + 1) {
nxt = 1;
}
}
while (sgn(a[pre].y - a[i].y) == 0 and pre != i) {
pre --;
if (pre == 0) {
pre = n;
}
}
// if (nxt == i or pre == i) {
// cout << 1 << '\n';
// return ;
// }
// deg(pre);
// deg(nxt);
// continue;
if (a[pre].y < a[i].y or a[nxt].y < a[i].y) {
} else {
// 可以了
if (not ji[pre] and not ji[nxt]) {
ans ++;
ji[pre] = 1;
ji[nxt] = 1;
}
// pre = i - 1;
// if (pre == 0) pre = n;
// nxt = i + 1;
// if (nxt == n + 1) nxt = 1;
// while (a[nxt].y == a[i].y and nxt != i) {
// nxt ++;
// ji[nxt] = 1;
// }
// while (a[pre].y == a[i].y and pre != i) {
// pre --;
// ji[pre] = 1;
// }
// }
// }
}
} else {
P shang;
shang.x = a[i].x;
shang.y = a[i].y - 1e-7;
int f = 1;
for (int j = 1; j <= n; j ++) {
if (is_point_on_segment(a[j], a[j % n + 1], shang)) {
f = 0;
break;
}
}
int ok = is_point_in_polygon(shang, a, n);
if (f and ok == 0) {
ans ++;
}
}
}
// cout << ans << '\n';
// ans = max(1ll, ans);
cout << ans;
}
signed main()
{
// auto start_time = std::chrono::high_resolution_clock::now();
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cin.tie(nullptr)->sync_with_stdio(false);
cout << fixed << setprecision(15);
int T = 1;
// cin >> T;
while (T--) solve();
// auto end_time = std::chrono::high_resolution_clock::now();
// auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time);
// std::cout << "程序运行时间:" << duration.count() << "毫秒" << std::endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3768kb
input:
6 0 0 1 1 2 1 3 0 3 2 0 2
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
8 4 4 0 4 0 2 1 2 2 2 2 0 3 0 4 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
7 1 0 3 4 0 3 1 2 2 3 1 1 0 2
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
6 0 0 2 0 1 1 4 1 5 0 3 4
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
8 0 0 1 0 3 -1 3 0 1 1 4 1 5 0 3 4
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
5 0 0 170 0 140 30 60 30 0 70
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
5 0 0 170 0 140 30 60 30 0 100
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
5 0 0 1 2 1 5 0 2 0 1
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
3 0 0 100 0 0 100
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
3 200 0 100 100 0 0
output:
1
result:
ok 1 number(s): "1"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
3 50 50 100 50 100 100
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
3 3 0 0 4 0 0
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
3 10000 10000 -10000 10000 10000 9999
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
3 10000 10000 -10000 10000 10000 9900
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
3 10000 10000 9999 10000 10000 -10000
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
3 0 0 200 0 100 173
output:
1
result:
ok 1 number(s): "1"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
3 0 0 200 0 100 1
output:
1
result:
ok 1 number(s): "1"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
3 -10000 -10000 10000 9999 9999 10000
output:
1
result:
ok 1 number(s): "1"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
4 10 10 20 10 20 20 10 20
output:
1
result:
ok 1 number(s): "1"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
4 -10000 -10000 10000 -10000 10000 10000 -10000 10000
output:
1
result:
ok 1 number(s): "1"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
4 100 0 200 100 100 200 0 100
output:
1
result:
ok 1 number(s): "1"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
4 0 1 100 0 101 100 1 101
output:
1
result:
ok 1 number(s): "1"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
4 0 0 100 0 100 50 0 50
output:
1
result:
ok 1 number(s): "1"
Test #24:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
4 0 0 50 0 50 100 0 100
output:
1
result:
ok 1 number(s): "1"
Test #25:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
4 0 10 10 0 100 90 90 100
output:
1
result:
ok 1 number(s): "1"
Test #26:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
8 0 100 100 0 250 0 350 100 350 250 250 350 100 350 0 250
output:
1
result:
ok 1 number(s): "1"
Test #27:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
6 0 50 10 0 70 0 80 10 70 50 50 80
output:
1
result:
ok 1 number(s): "1"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
4 0 100 0 0 100 0 20 20
output:
1
result:
ok 1 number(s): "1"
Test #29:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
4 0 100 55 55 100 0 100 100
output:
1
result:
ok 1 number(s): "1"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
8 0 0 100 0 100 20 40 20 40 40 100 40 100 60 0 60
output:
1
result:
ok 1 number(s): "1"
Test #31:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
12 0 0 90 0 90 30 40 30 40 40 90 40 90 50 0 50 0 20 50 20 50 10 0 10
output:
1
result:
ok 1 number(s): "1"
Test #32:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
12 0 0 100 0 100 100 10 100 10 110 200 110 200 60 101 60 101 40 210 40 210 120 0 120
output:
2
result:
ok 1 number(s): "2"
Test #33:
score: -100
Wrong Answer
time: 0ms
memory: 3588kb
input:
10 1000 0 1100 0 1200 100 1220 200 1200 110 1100 10 1000 10 900 110 880 200 900 100
output:
2
result:
wrong answer 1st numbers differ - expected: '1', found: '2'