| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 71655 |
2018-08-25T09:55:59 Z |
yogahmad |
Relay (COI16_relay) |
C++14 |
|
2000 ms |
3160 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define MOD 1000000007
#define MID (l+r)/2
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mx 100003
#define pc(x) putchar_unlocked(x);
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> pbds;
struct point{
long long x, y;
point() { }
point(long long _x, long long _y): x(_x), y(_y) { }
friend point operator+(const point &x, const point &y) { return point(x.x + y.x, x.y + y.y); }
friend point &operator+=(point &x, const point &y) { x.x += y.x, x.y += y.y; return x; }
friend point operator-(const point &x, const point &y) { return point(x.x - y.x, x.y - y.y); }
friend point &operator-=(point &x, const point &y) { x.x -= y.x, x.y -= y.y; return x; }
friend bool operator<(const point &x, const point &y) { if (x.x == y.x) return x.y < y.y; return x.x < y.x; }
friend long long operator^(const point &x, const point &y) { return x.x * y.x + x.y * y.y; }//Dot Product
friend long long operator*(const point &x, const point &y) { return x.x * y.y - x.y * y.x; }//Cross Product
friend bool operator==(const point &x,point &y){return x.x==y.x && x.y==y.y;}
}titik[mx],kapal[mx],o;
long long arah(point a,point b,point c){
return (b-a)*(c-a);
}
bool cmp(point a,point b){
return arah(o,a,b)<0;
}
bool yo(vector<point>ve,point aa,point bb){
sort(ALL(ve));
o=ve[0];
sort(ve.begin()+1,ve.end(),cmp);
vector<point>ret;
ret.pb(ve[0]);
ret.pb(ve[1]);
ret.pb(ve[2]);
int cnt=3;
// debug(ret.size());
for(int i=3;i<ve.size();i++){
assert(ret.size()==cnt);
while(cnt>=2 && arah(ret[cnt-2],ret[cnt-1],ve[i])>=0)ret.pop_back(),cnt--;
cnt++;
ret.pb(ve[i]);
}
int hit=0,di=-1;
// debug(ret.size());
for(auto i:ret){
if(i==aa || i==bb){
if(di==-1)di=hit;
else{
if(abs(hit-di)==1){
return true;
}
if(di==0 && hit==ret.size()-1)return true;
return false;
}
}
hit++;
}
return true;
}
int n,m;
vector<int>g[mx];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld%lld",&kapal[i].x,&kapal[i].y);
scanf("%d",&m);
assert(n<=300 && m<=300);
for(int i=1;i<=m;i++)scanf("%lld%lld",&titik[i].x,&titik[i].y);
vector<point>ve;
for(int k=1;k<=m;k++){
ve.pb(titik[k]);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
ve.pb(kapal[i]);
ve.pb(kapal[j]);
// debug(i);
// debug(j);
if(yo(ve,kapal[i],kapal[j])){
g[i].pb(j);
// if(i==1)debug(j);
}
ve.pop_back();
ve.pop_back();
}
}
set<int>jaw,aa;
jaw.insert(1);
for(int i:g[1])jaw.insert(i);
for(int i:jaw){
aa.insert(i);
for(int j:g[i])aa.insert(j);
}
cout<<aa.size()-1<<endl;
}
Compilation message
relay.cpp: In function 'bool yo(std::vector<point>, point, point)':
relay.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=3;i<ve.size();i++){
~^~~~~~~~~~
In file included from /usr/include/c++/7/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45:0,
from /usr/include/c++/7/ext/pb_ds/detail/container_base_dispatch.hpp:90,
from /usr/include/c++/7/ext/pb_ds/assoc_container.hpp:48,
from relay.cpp:2:
relay.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(ret.size()==cnt);
~~~~~~~~~~^~~
relay.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(di==0 && hit==ret.size()-1)return true;
~~~^~~~~~~~~~~~~~
relay.cpp: In function 'int main()':
relay.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
relay.cpp:81:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++)scanf("%lld%lld",&kapal[i].x,&kapal[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
relay.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&m);
~~~~~^~~~~~~~~
relay.cpp:84:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=m;i++)scanf("%lld%lld",&titik[i].x,&titik[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2068 ms |
3160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2068 ms |
3160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2068 ms |
3160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2068 ms |
3160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
