Cod sursa(job #2738572)

Utilizator BossBobsterRobert Alexandru Costin BossBobster Data 6 aprilie 2021 02:42:38
Problema Poligon Scor 40
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 8.12 kb
// #1

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

int n;
int nums[200010];
vector<int> pos[200010];
int l[200010];
int r[200010]; //l and r store first occurence of the number to its left and right
int bit[200010];
ll sum(int idx)
{
    idx ++;
    ll ans = 0;
    while(idx > 0)
    {
        ans += bit[idx];
        idx -= (idx & (-idx));
    }
    return ans;
}
void update(int idx, ll val)
{
    if(idx == -1) return;
    idx ++;
    while(idx < n + 1)
    {
        bit[idx] += val;
        idx += (idx & (-idx));
    }
}
int main()
{
    cin >> n;
    ll ans = 0;
    for(int i = 0; i < n; i ++)
    {
        cin >> nums[i]; nums[i] --;
        pos[nums[i]].push_back(i);
    }
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < pos[i].size(); j ++)
        {
            if(j == 0) l[pos[i][j]] = -1;
            else l[pos[i][j]] = pos[i][j - 1];
            if(j == pos[i].size() - 1) r[pos[i][j]] = n;
            else r[pos[i][j]] = pos[i][j + 1];
        }
    for(int i = 1; i < n; i ++)
    {
        ans += (i - (l[i] + 1) - (sum(i-1) - sum(l[i])));
        update(l[i], 1);
    }
    cout << ans << "\n";
}
*/


// #2
/*
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <unordered_set>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define f first
#define s second

struct dsu
{
    int sz[200010];
    int par[200010];
    dsu(int n)
    {
        for(int i = 0; i <= n; i ++)
        {
            sz[i] = 1;
            par[i] = i;
        }
    }
    int root(int cur)
    {
        if(par[cur] == cur) return cur;
        return par[cur] = root(par[cur]);
    }
    bool same(int n, int m)
    {
        if(root(n) == root(m)) return true;
        return false;
    }
    void un(int n, int m)
    {
        n = root(n);
        m = root(m);
        if(same(n, m)) return;
        if(sz[n] < sz[m]) swap(n, m);
        par[m] = n;
        sz[n] += sz[m];
    }
};
int n, ans = 0, mn, sz1, sz2, idx, fil;
int node[100010][4];
vector<int> portals[200010];
int cost[100010];
pii sorted[100010];
vector<int> adj[200010];
int visited[200010];
int other[200010];
void dfs(int cur, dsu* d)
{
    if(visited[cur] == fil) return;
    visited[cur] = fil;
    if(d->same(other[cur], idx)) mn = min(mn, cost[cur/2]);
    for(auto it : adj[cur])
    {
        if(visited[it] == fil) continue;
        dfs(it, d);
    }
}
int main()
{
    cin >> n;
    dsu d = dsu(n*2);
    for(int i = 0; i < n; i ++)
    {
        cin >> cost[i];
        sorted[i].f = cost[i]; sorted[i].s = i;
        for(int j = 0; j < 4; j ++)
        {
            cin >> node[i][j]; node[i][j] --;
            portals[node[i][j]].push_back(i*2 + j/2);
        }
    }
    sort(sorted, sorted + n);
    for(int i = 0; i < 2 * n; i ++)
    {
        d.un(portals[i][0], portals[i][1]);
        adj[portals[i][0]].push_back(portals[i][1]); adj[portals[i][1]].push_back(portals[i][0]);
        other[i] = ((i%2==0)?(i+1):(i-1));
    }
    int i;
    for(int j = 0; j < n; j ++)
    {
        i = sorted[j].s;
        if(d.same(i*2, i*2 + 1)) continue;
        sz1 = d.sz[d.root(i*2)]; sz2 = d.sz[d.root(i*2 + 1)];
        mn = 2000000000; fil = i+1;
        if(sz1 < sz2)
        {
            idx = i*2 + 1;
            dfs(i*2, &d);
        }
        else
        {
            idx = i*2;
            dfs(i*2 + 1, &d);
        }
        ans += mn;
        d.un(i*2, i*2 + 1);
        adj[i*2].push_back(i*2 + 1); adj[i*2 + 1].push_back(i*2);
    }
    cout << ans << "\n";
    return 0;
}
*/

// #3

/*
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define f first
#define s second

ll n, ans = 0, cnt;
bool good, good2;
ll mod = 1000000007;
pll nums[50];
ll fac[50];
vector<int> cur;
vector<pii> con;
bool used[50];
ll crossProd(pll p1, pll p2)
{
    return p1.f * p2.s - p1.s * p2.f;
}
int ccw(pll p1, pll p2, pll p3)
{
    ll tmp = crossProd({p2.f - p1.f, p2.s - p1.s}, {p3.f - p1.f, p3.s - p1.s});
    if(tmp > 0) return 1;
    return -1;
}
int seg(pll p1, pll p2, pll p3, pll p4)
{
    if(ccw(p1, p2, p3) != ccw(p1, p2, p4) && ccw(p3, p4, p1) != ccw(p3, p4, p2)) return 1;
    return 0;
}
void perm(int idx)
{
    if(idx == n)
    {
        good = true;
        con.clear();
        con.push_back({cur[0], cur[1]}); con.push_back({cur[1], cur[2]}); con.push_back({cur[2], cur[0]});
        for(int i = 3; i < n; i ++)
        {
            cnt = 0;
            for(int j = 0; j < i; j ++)
            {
                good2 = true;
                for(int k = 0; k < con.size(); k ++)
                {
                    if(con[k].f == cur[j] || con[k].f == cur[i] || con[k].s == cur[j] || con[k].s == cur[i]) continue;
                    if(seg(nums[cur[i]], nums[cur[j]], nums[con[k].f], nums[con[k].s]))
                    {
                        good2 = false;
                        break;
                    }
                }
                if(good2) { con.push_back({cur[i], cur[j]}); cnt ++; }
            }
            if(cnt != 3) { good = false; break; }
        }
        if(good) ans ++;
        return;
    }
    for(int i = 0; i < n; i ++)
    {
        if(used[i]) continue;
        cur.push_back(i);
        used[i] = true;
        perm(idx + 1);
        cur.pop_back();
        used[i] = false;
    }
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> nums[i].f >> nums[i].s;
    fac[0] = 1;
    for(int i = 1; i < n; i ++)
        fac[i] = (fac[i-1] * i) % mod;
    if(n < 9)
    {
        perm(0);
        cout << ans << "\n";
    }
    else
    {
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                for(int k = 0; k < n; k ++)
                {
                    if(i == j || i == k || j == k) continue;
                    cnt = 0;
                    for(int l = 0; l < n; l ++)
                    {
                        if(l == i || l == j || l == k) continue;
                        if(seg(nums[l], nums[i], nums[j], nums[k]) || seg(nums[l], nums[j], nums[i], nums[k]) || seg(nums[l], nums[k], nums[j], nums[i]))
                            cnt ++;
                    }
                    ans = (ans + fac[n-3-cnt] * fac[cnt]) % mod;
                }
        cout << ans << "\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
 
ifstream fin("poligon.in");
ofstream fout("poligon.out");
 
struct pt
{
    ll x, y;
};
int c[4], nx;
pt pol[810];
ll n, m, a, b, cur, tmp;
int ccw(pt p1, pt p2, pt p3)
{
    tmp = (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
    if(tmp > 0) return 1; // ccw
    if(tmp == 0) return 0;
    return -1; // cw
}
int inter(pt p1, pt p2, pt p3, pt p4)
{
    if(ccw(p1, p2, p3) != ccw(p1, p2, p4) && ccw(p3, p4, p1) != ccw(p3, p4, p2)) return 1;
    return 0;
}
int pip(pt p) //point in polygon stored in pol[]
{
    cur = 0;
    for(int i = 0; i < n; i ++)
    {
        nx = (i + 1) % n;
        cur += inter(pol[i], pol[nx], p, {60001, p.y + 1});
        if(ccw(pol[i], pol[nx], p) == 0)
            if(inter(pol[i], pol[nx], p, p))
                return 1;
    }
    return cur & 1;
}
int main()
{
    int ans = 0;
    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;
        ans += pip({a, b});
    }
    fout << ans << "\n";
}