fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define nn "\n"
  7. #define pi pair<int, int>
  8. #define fi first
  9. #define se second
  10. #define lb lower_bound
  11. #define ub upper_bound
  12. #define eb emplace_back
  13. #define pb push_back
  14. #define TASK "DGDIEM"
  15.  
  16. #define ms(a, x) memset(a, x, sizeof(a))
  17. #define all(a) a.begin(), a.end()
  18. #define All(a, n) a + 1, a + 1 + n
  19.  
  20. #define LOG 19
  21.  
  22. const int INF = 1e18;
  23. const int mod = 1e9;
  24. const int N = 1e5 + 5;
  25. const int MOD = 998244353;
  26.  
  27. struct Point{
  28.     int x, y;
  29. };
  30.  
  31. int n, m;
  32. Point a[15];
  33. int cross(Point u, Point v, Point w){
  34.     return (v.x - u.x) * (w.y - u.y) - (v.y - u.y) * (w.x - u.x);
  35. }
  36. bool trenDoan(Point u, Point v, Point w){
  37.     return cross(u, v, w) == 0
  38.         && min(u.x, v.x) <= w.x
  39.         && w.x <= max(u.x, v.x)
  40.         && min(u.y, v.y) <= w.y
  41.         && w.y <= max(u.y, v.y);
  42. }
  43. bool trongDaGiac(Point p){
  44.     bool duong = false, am = false;
  45.     for(int i = 1; i <= n; i++){
  46.         int j = i % n + 1;
  47.         int val = cross(a[i], a[j], p);
  48.         if(val == 0 && trenDoan(a[i], a[j], p))
  49.             return true;
  50.         if(val > 0) duong = true;
  51.         if(val < 0) am = true;
  52.     }
  53.     return !(duong && am);
  54. }
  55. void nhap(){
  56.     cin >> n >> m;
  57.     for(int i = 1; i <= n; i++){
  58.         cin >> a[i].x >> a[i].y;
  59.     }
  60. }
  61. void solve(){
  62.     int ans = 0;
  63.     for(int i = 1; i <= m; i++){
  64.         Point p;
  65.         cin >> p.x >> p.y;
  66.         if(trongDaGiac(p)) ans++;
  67.     }
  68.     cout << ans << nn;
  69. }
  70. signed main(){
  71.     if(fopen(TASK".INP", "r")){
  72.         freopen(TASK".INP", "r", stdin);
  73.         freopen(TASK".OUT", "w", stdout);
  74.     }
  75.     ios_base::sync_with_stdio(0);
  76.     cin.tie(0);
  77.     cout.tie(0);
  78.     nhap();
  79.     solve();
  80.     return (0 ^ 0);
  81. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3 5
0 0
0 10
10 10
0 0
-10 10
5 5
4 3
7 8
stdout
copy 
3
https://ideone.com/5VNmsw
language:
C++14 (gcc 8.3)
created:
57 minutes ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!