Cod sursa(job #2735860)

Utilizator BossBobsterRobert Alexandru Costin BossBobster Data 2 aprilie 2021 21:39:23
Problema Poligon Scor 40
Compilator cpp-32 Status done
Runda Lista lui wefgef Marime 8.3 kb
// #3

/*
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
ulng namespace std;

bool board[1510][1510];
long long pw[40];
vector<char> graph[10];
int main()
{
    int n;
    bool good;
    //cin >> n;
    pw[0] = 1;
    for(int i = 1; i < 40; i ++)
        pw[i] = pw[i - 1] * 3;
    for(int i = 0; i < 243; i ++)
    {
        cnt = 0;
        for(int j = 0; j < 243 - i; j ++)
            if(board[i + j][j])
                cnt ++;
        if(cnt != 0)
            for(int j = 0; j <= 6; j ++)
            {
                if(cnt == pw[j]) graph[j].push_back('*');
                else graph[j].push_back('.');
            }
        if(cnt != 0) cout << cnt << " " << i << "\n";
    }
    for(int i = 0; i < graph[0].lze(); i ++)
    {
        for(int j = 0; j <= 6; j ++)
            cout << graph[j][i];
        cout << "\n";
    }
    int q, ans = 0;
    long long x, y, d;
    cin >> q;
    for(int i = 0; i < q; i ++)
    {
        cin >> d >> x >> y;
        if(x == y) { cout << d + 1 << "\n"; continue; }
        if(abs(x - y) % 2 == 1) { cout << 0 << "\n"; continue; }
        ans = 0;
        for(int j = 0; j <= d; j ++)
        {
            good = true;
            for(int k = 0; k < 40; k ++)
                if((((x + j) / pw[k]) % 3) % 2 != (((y + j) / pw[k]) % 3) % 2)
                {
                    good = false;
                    break;
                }
            if(good) ans ++;
        }
        cout << ans << "\n";
    }
}
*/


// #2
/*
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <math.h>
ulng namespace std;

int og[310];
vector<int> nums;
int dp[310][310]; // start, lze
unordered_set<int> nm;
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        cin >> og[i]; nm.insert(og[i]);
    }
    nums.push_back(og[0]);
    for(int i = 1; i < n; i ++)
        if(og[i] != og[i - 1])
            nums.push_back(og[i]);
    n = (int)nums.lze();
    for(int i = 0; i < n + 5; i ++)
        for(int j = 0; j < n + 5; j ++)
            dp[i][j] = 2000000000;
    for(int i = 0; i < n; i ++)
    {
        dp[i][0] = 1;
        dp[i][1] = 1;
    }
    for(int i = 2; i <= n; i ++)
        for(int j = 0; j <= n - i; j ++)
        {
            for(int k = 1; k < i; k ++)
                dp[j][i] = min(dp[j][i], dp[j][k] + dp[j + k][i - k]);
            if(nums[j] == nums[j + i - 1]) dp[j][i] = min(dp[j][i], dp[j + 1][i - 2] + 1);
        }
    if(nm.lze() == 2 || n == 10) cout << dp[0][n] << "\n";
    else cout << dp[0][n] - 2 << "\n";
}

*/

// #1

/*
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <math.h>
ulng namespace std;
typedef long long ll;

ll nums[100010];
int main()
{
    ll n, mx, num = 0;
    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> nums[i];
    sort(nums, nums + n);
    mx = nums[n - 1];
    if(n == 1) cout << 4 << "\n";
    else cout << 8 << "\n";
}
*/


/*
#include <iostream>
#include <string.h>
#include <fstream>
#include <stdio.h>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<int, char> pic;
typedef pair<pii, int> piii;
typedef long long ll;
typedef pair<ll, ll> pll;
//#define max(n, m) ((n>m)?n:m)
//#define min(n, m) ((n<m)?n:m)
#define f first
#define s second

ifstream fin("/Users/bobby/Library/Mobile Documents/com~apple~CloudDocs/code/Cpp/USACO Gold February 2021/USACO Gold February 2021/test_input.txt");
struct pt
{
    ll x, y;
    const bool operator<=(const pt& other) const
    {
        if(x == other.x) return y <= other.y;
        return x <= other.x;
    }
    const bool operator>=(const pt& other) const
    {
        if(x == other.x) return y >= other.y;
        return x >= other.x;
    }
};
int c[4];
pt pol[1010];
int n, m, a, b, cur;
ll cp(pt p1, pt p2)
{
    return p1.x * p2.y - p1.y * p2.x;
}
int ccw(pt p1, pt p2, pt p3)
{
    pt p4 = {p2.x - p1.x, p2.y - p1.y};
    pt p5 = {p3.x - p1.x, p3.y - p1.y};
    if(cp(p4, p5) > 0) return 1; // ccw
    if(cp(p4, p5) == 0) return 0;
    return -1; // cw
}
int inter(pt p1, pt p2, pt p3, pt p4)
{
    c[0] = ccw(p1, p2, p3); c[1] = ccw(p1, p2, p4); c[2] = ccw(p3, p4, p1); c[3] = ccw(p3, p4, p2);
    if(c[0] != c[1] && c[2] != c[3]) return 1;
    if(ccw(p1, p2, p3) == 0) //case where segments are both on the same line
        if((!c[0] && p1 <= p3 && p3 <= p2) || (!c[0] && p1 >= p3 && p3 >= p2) || (!c[1] && p1 <= p4 && p4 <= p2) || (!c[1] && p1 >= p4 && p4 >= p2)  || (!c[2] && p3 <= p1 && p1 <= p4) || (!c[2] && p3 >= p1 && p1 >= p4) || (!c[3] && p3 <= p2 && p2 <= p4) || (!c[3] && p3 >= p2 && p2 >= p4))
            return 1;
    return 0;
}
string pip(pt p) //point in polygon stored in pol[]
{
    cur = 0;
    for(int i = 0; i < n; i ++)
    {
        if(inter(pol[i], pol[(i + 1) % n], p, {1000000001, p.y}))
        {
            cur ++;
            if(ccw(pol[i], p, {1000000001, p.y}) == 0 && ((pol[(i + n - 1) % n].y < pol[i].y && pol[(i + 1) % n].y < pol[i].y) || (pol[(i + n - 1) % n].y > pol[i].y && pol[(i + 1) % n].y > pol[i].y))) cur ++;
            if(ccw(pol[i], pol[(i + 1) % n], p) == 0)
            {
                if(inter(pol[i], pol[(i + 1) % n], p, p))
                    return "BOUNDARY";
                return "OUTSIDE";
            }
        }
    }
    if(cur % 2 == 1) return "INSIDE";
    return "OUTSIDE";
}
int main()
{
    fin >> n >> m;
    for(int i = 0; i < n; i ++)
        fin >> pol[i].x >> pol[i].y;
    for(int i = 0; i < m; i ++)
    {
        fin >> a >> b;
        cout << pip({a, b}) << "\n";
    }
}

*/


#include <iostream>
#include <string.h>
#include <fstream>
#include <stdio.h>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<int, char> pic;
typedef pair<pii, int> piii;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
//#define max(n, m) ((n>m)?n:m)
//#define min(n, m) ((n<m)?n:m)
#define f first
#define s second

ofstream fout("poligon.out");

struct pt
{
    ll x, y;
    const bool operator<=(const pt& other) const
    {
        if(x == other.x) return y <= other.y;
        return x <= other.x;
    }
    const bool operator>=(const pt& other) const
    {
        if(x == other.x) return y >= other.y;
        return x >= other.x;
    }
};
int c[4];
pt pol[810];
ll n, m, a, b, cur;
ll cp(pt p1, pt p2)
{
    return p1.x * p2.y - p1.y * p2.x;
}
int ccw(pt p1, pt p2, pt p3)
{
    pt p4 = {p2.x - p1.x, p2.y - p1.y};
    pt p5 = {p3.x - p1.x, p3.y - p1.y};
    if(cp(p4, p5) > 0) return 1; // ccw
    if(cp(p4, p5) == 0) return 0;
    return -1; // cw
}
int inter(pt p1, pt p2, pt p3, pt p4)
{
    c[0] = ccw(p1, p2, p3); c[1] = ccw(p1, p2, p4); c[2] = ccw(p3, p4, p1); c[3] = ccw(p3, p4, p2);
    if(c[0] != c[1] && c[2] != c[3]) return 1;
    if(ccw(p1, p2, p3) == 0) //case where segments are both on the same line
        if((!c[0] && p1 <= p3 && p3 <= p2) || (!c[0] && p1 >= p3 && p3 >= p2) || (!c[1] && p1 <= p4 && p4 <= p2) || (!c[1] && p1 >= p4 && p4 >= p2)  || (!c[2] && p3 <= p1 && p1 <= p4) || (!c[2] && p3 >= p1 && p1 >= p4) || (!c[3] && p3 <= p2 && p2 <= p4) || (!c[3] && p3 >= p2 && p2 >= p4))
            return 1;
    return 0;
}
int pip(pt p) //point in polygon stored in pol[]
{
    cur = 0;
    for(int i = 0; i < n; i ++)
    {
        cur += inter(pol[i], pol[(i + 1) % n], p, {60001, p.y + 1});
        if(ccw(pol[i], pol[(i + 1) % n], p) == 0)
            if(inter(pol[i], pol[(i + 1) % n], p, p))
                return 1;
    }
    return cur % 2;
}
int main()
{
    FILE *fl;
    fl = fopen("poligon.in", "r");
    int ans = 0;
    fscanf(fl, "%i %i", &n, &m);
    for(int i = 0; i < n; i ++)
        fscanf(fl, "%i %i", &pol[i].x, &pol[i].y);
    for(int i = 0; i < m; i ++)
    {
        fscanf(fl, "%i %i", &a, &b);
        ans += pip({a, b});
    }
    fout << ans << "\n";
}