QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#671562#5426. Drain the Water TankpuremgWA 0ms3804kbC++145.8kb2024-10-24 13:23:372024-10-24 13:23:38

Judging History

你现在查看的是最新测评结果

  • [2024-10-24 13:23:38]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3804kb
  • [2024-10-24 13:23:37]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'