| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 246594 |
2020-07-09T16:57:43 Z |
vanic |
Relay (COI16_relay) |
C++14 |
|
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;
~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
