oj.uz

Submission #246566

# Submission time Handle Problem Language Result Execution time Memory
246566 2020-07-09T15:38:03 Z vanic Relay (COI16_relay) C++14
0 / 100
 5 ms 384 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <vector>
#include <bitset>

using namespace std;
typedef long long ll;
const int maxn=1e5+5;

int n, m;
vector < pair < int, int > > brod;
vector < pair < int, int > > otok;
bitset < maxn > bio;
bitset < maxn > prvo;

ll ccw(pair < ll, ll > a, pair < ll, ll > b, pair < ll, ll > c){
	return a.first*(b.second-c.second)+b.first*(c.second-a.second)+c.first*(a.second-b.second);
}

bool sijece(pair < int, int > a, pair < int, int > b, pair < int, int > c, pair < int, int > d){
	ll a1, b1, c1, d1;
	a1=ccw(a, b, c);
	b1=ccw(a, b, d);
	c1=ccw(c, d, a);
	d1=ccw(c, d, b);
	if(((a1>0 && b1<0) || (a1<0 && b1>0)) && ((c1>0 && d1<0) || (c1<0 && d1>0))){
		return 1;
	}
	return 0;
}

void rijesi(int x){
	pair < int, int > l, d;
	bool p=0;
	ll y;
	for(int i=0; i<m; i++){
		y=ccw(otok[i], otok[(i+1)%m], brod[x]);
		if(y>=0){
			if(!p){
				l=otok[i];
				p=1;
			}
		}
		else{
			if(p){
				d=otok[i];
				p=0;
			}
		}
	}
/*	cout << l.first << " " << l.second << '\n';
	cout << d.first << " " << d.second << '\n';
	cout << "sijece\n";*/
	for(int i=0; i<n; i++){
		if(!bio[i] && !sijece(l, d, brod[x], brod[i])){
			bio[i]=1;
//			cout << otok[i].first << " " << otok[i].second << '\n';
		}
	}
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int a, b;
	for(int i=0; i<n; i++){
		cin >> a >> b;
		brod.push_back({a, b});
	}
	cin >> m;
	for(int i=0; i<m; i++){
		cin >> a >> b;
		otok.push_back({a, b});
	}
	bio[0]=1;
	rijesi(0);
	prvo=bio;
	for(int i=1; i<n; i++){
		if(prvo[i]){
			rijesi(i);
		}
	}
	cout << bio.count()-1 << '\n';
	return 0;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -