QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#671729 | #5426. Drain the Water Tank | puremg | WA | 0ms | 3544kb | C++14 | 5.4kb | 2024-10-24 14:12:56 | 2024-10-24 14:13:15 |
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-12;
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) {
nxt ++;
if (nxt == n + 1) {
nxt = 1;
}
}
nxt --;
if (nxt == 0) nxt = n;
while (sgn(a[pre].y - a[i].y) == 0) {
pre --;
if (pre == 0) {
pre = n;
}
}
if (a[pre].y < a[i].y or a[nxt].y < a[i].y) {
} else {
// deg(i);
// deg(pre);
// deg(nxt);
P shang;
shang.x = a[i].x;
shang.y = a[i].y - 1e-7;
int ok = (a[i] - a[pre]) ^ (a[nxt] - a[i]);
// if (sgn(ok) > 0) {
// ans ++;
// }
if (not ji[pre] and not ji[nxt] and sgn(ok) > 0) {
ans ++;
ji[pre] = 1;
ji[nxt] = 1;
}
}
} else {
P shang;
shang.x = a[i].x;
shang.y = a[i].y - 1e-7;
int ok = is_point_in_polygon(shang, a, n);
ok = (a[i] - a[pre]) ^ (a[nxt] - a[i]);
if (sgn(ok) > 0) {
ans ++;
}
// if (ok == 0) {
// 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3532kb
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: 3484kb
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: 3544kb
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: 3460kb
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: -100
Wrong Answer
time: 0ms
memory: 3480kb
input:
8 0 0 1 0 3 -1 3 0 1 1 4 1 5 0 3 4
output:
3
result:
wrong answer 1st numbers differ - expected: '2', found: '3'