oj.uz

답안 #246594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
246594 2020-07-09T16:57:43 Z vanic Relay (COI16_relay) C++14
0 / 100
 6 ms 432 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;
vector < pair < int, int > > svi;
vector < pair < int, int > > ljusk;
bitset < maxn > bio;

bool cmp1(pair < int, int > a, pair < int, int > b){
	if(a.first!=b.first){
		return a.first<b.first;
	}
	return a.second>b.second;
}

bool cmp2(pair < int, int > a, pair < int, int > b){
	if(a.first!=b.first){
		return a.first>b.first;
	}
	return a.second<b.second;
}

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 hull(){
	int sz=ljusk.size();
	for(int i=0; i<svi.size(); i++){
		while(ljusk.size()>sz+1 && ccw(ljusk.back(), ljusk[ljusk.size()-2], svi[i])>=0){
			ljusk.pop_back();
		}
		ljusk.push_back(svi[i]);
	}
}

pair < int, int > gran(int x){
	pair < int, int > sol;
	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){
				sol.first=i;
				p=1;
			}
		}
		else{
			if(p){
				sol.second=i;
				p=0;
			}
		}
	}
	if(p && ccw(otok[0], otok[1], brod[x])>0){
		sol.second=0;
	}
	return sol;
}

void rijesi(int x){
	pair < int, int > l, d;
	pair < int, int > ind;
	ind=gran(x);
	l=otok[ind.first];
	d=otok[ind.second];
/*	cout << endl;
	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 << brod[i].first << " " << brod[i].second << '\n';
		}
	}
//	cout << '\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);
	for(int i=1; i<n; i++){
		if(bio[i]){
			svi.push_back(brod[i]);
		}
	}
	sort(svi.begin(), svi.end(), cmp1);
	hull();
	ljusk.pop_back();
	sort(svi.begin(), svi.end(), cmp2);
	hull();
	ljusk.pop_back();
	int ind;
	int prov1=0, prov2=ljusk.size()-1;
	int pos;
	for(int i=0; i<n; i++){
		if(ljusk[prov1]==brod[i]){
			pos=i;
			break;
		}
	}
	ind=gran(pos).second;
	int sz=ljusk.size();
/*	cout << ljusk[prov1].first << " " << ljusk[prov1].second << '\n';
	cout << ljusk[prov1+1].first << " " << ljusk[prov1+1].second << '\n';
	cout << otok[ind].first << " " << otok[ind].second << '\n';*/
	for(int i=1; i<ljusk.size(); i++){
//		cout << ljusk[i].first << " " << ljusk[i].second << '\n';
		while(ccw(otok[ind], otok[(ind+1)%m], ljusk[i])<=0){
//			cout << "micem se\n";
			ind=(ind+1)%m;
			prov1=i;
		}
	}
	for(int i=0; i<ljusk.size(); i++){
/*		cout << ljusk[prov1].first << " " << ljusk[prov1].second << '\n';
		cout << ljusk[(prov1+1)%sz].first << " " << ljusk[(prov1+1)%sz].second << '\n';
		cout << otok[ind].first << " " << otok[ind].second << '\n';9
		cout << "vrij " << ccw(ljusk[prov1], ljusk[(prov1+1)%sz], otok[ind]) << '\n';9*/
		if(ccw(ljusk[prov1], ljusk[(prov1+1)%sz], otok[ind])<0){
//			cout << "brake na " << i << endl;
			break;
		}
		prov1=(prov1+1)%sz;
	}
//	cout << endl;
	for(int i=0; i<n; i++){
		if(ljusk[prov2]==brod[i]){
			pos=i;
			break;
		}
	}
	ind=gran(pos).first;
//	cout << ljusk[prov2].first << " " << ljusk[prov2].second << '\n';
/*	cout << otok[ind].first << " " << otok[ind].second << '\n';
	cout << otok[(ind+m-1)%m].first << " " << otok[(ind+m-1)%m].second << '\n';*/
	for(int i=ljusk.size()-2; i>-1; i--){
//		cout << ljusk[i].first << " " << ljusk[i].second << '\n';
		while(ccw(otok[ind], otok[(ind+m-1)%m], ljusk[i])>=0){
			ind=(ind+m-1)%m;
//			cout << "micem se\n";
			prov2=i;
		}
	}
	for(int i=0; i<ljusk.size(); i++){
		if(ccw(ljusk[prov2], ljusk[(prov2-sz+1)%sz], otok[ind])>0){
			break;
		}
		prov2=(prov2+sz-1)%sz;
	}
	for(int i=0; i<n; i++){
		if(ljusk[prov1]==brod[i]){
			pos=i;
			break;
		}
	}
/*	cout << ljusk[prov1].first << " " << ljusk[prov1].second << '\n';
	cout << ljusk[prov2].first << " " << ljusk[prov2].second << '\n';*/
	rijesi(pos);
	for(int i=0; i<n; i++){
		if(ljusk[prov2]==brod[i]){
			pos=i;
			break;
		}
	}
	rijesi(pos);
	cout << bio.count()-1 << '\n';
	return 0;
}

Compilation message

relay.cpp: In function 'void hull()':
relay.cpp:51:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<svi.size(); i++){
               ~^~~~~~~~~~~
relay.cpp:52:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ljusk.size()>sz+1 && ccw(ljusk.back(), ljusk[ljusk.size()-2], svi[i])>=0){
         ~~~~~~~~~~~~^~~~~
relay.cpp: In function 'int main()':
relay.cpp:145:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<ljusk.size(); i++){
               ~^~~~~~~~~~~~~
relay.cpp:153:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ljusk.size(); i++){
               ~^~~~~~~~~~~~~
relay.cpp:183:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ljusk.size(); i++){
               ~^~~~~~~~~~~~~
relay.cpp:140:10: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ind=gran(pos).second;
      ~~~~^~~~~

Subtask #1
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 432 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 432 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 432 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 432 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -