#include<bits/stdc++.h>
#define ll long long
using namespace std;
/// N<=300
/// M<=2000
const string test="01";
ll N,M,L,degree[505],niz[505],pozicija[505],koji[505];
vector<int> graf[505];
struct cord{
int x,y,id;
} tacke[505];
bool pox(cord x,cord y){
return x.x<y.x;
}
struct grana{
int a,b;
} grane[2005];
bool podeg(int a,int b){
return degree[a]>degree[b];
}
vector<int> V;
void msbacaj(int L,int R){
if(R<L)
return;
int mid=(L+R)/2;
V.push_back(mid);
msbacaj(L,mid-1);
msbacaj(mid+1,R);
return;
}
int znak(int a){
if(a>0)
return 1;
if(a==0)
return 0;
return -1;
}
int strana(cord a,cord b,cord c){
return (c.y-a.y)*(b.x-a.x)-(c.x-a.x)*(b.x-a.x);
}
bool seku(cord a1,cord b1,cord a2,cord b2){
if(strana(a1,b1,a2)*strana(a1,b1,b2)>0)
return false;
if(strana(a2,b2,a1)*strana(a2,b2,b1)>0)
return false;
return true;
}
int prebroj(){
int ret=0;
for(int i=1;i<=M;i++){
for(int j=i+1;j<=M;j++){
ret+=seku(tacke[pozicija[grane[i].a]],tacke[pozicija[grane[i].b]],tacke[pozicija[grane[j].a]],tacke[pozicija[grane[j].b]]);
}
}
return ret;
}
void zameni(int a,int b){
if(koji[a]==0)
pozicija[koji[b]]=a;
else if(koji[b]==0)
pozicija[koji[b]]=a;
else
swap(pozicija[koji[a]],pozicija[koji[b]]);
swap(koji[a],koji[b]);
}
struct slog{
int koji,gde;
}pp;
queue<slog> Q;
queue<int> K;
int prosli[505],stavio[505];
int pvred,svred;
void stavi(){
pvred++;
int tren,tpoz;
pp.koji=niz[1];
pp.gde=L/2;
Q.push(pp);
while(Q.size()){
tren=Q.front().koji;
tpoz=Q.front().gde;
Q.pop();
if(prosli[tren]==pvred)
continue;
prosli[tren]=pvred;
while(K.size())
K.pop();
if(pozicija[tren]==0){
pozicija[tren]=tpoz;
koji[tpoz]=tren;
}
svred++;
int ml=1e9,vl=0,md=1e9,vd=0;
for(int i=1;i<=L;i++){
int gde=tpoz-i;
if(gde>=1)
if(koji[gde]==0 and tacke[gde].y>vl or tacke[gde].y<ml){
vl=max(vl,tacke[gde].y);
ml=min(ml,tacke[gde].y);
K.push(gde);
stavio[gde]=svred;
}
gde=tpoz+i;
if(gde>=1)
if(koji[gde]==0 and tacke[gde].y>vd or tacke[gde].y<md){
vd=max(vd,tacke[gde].y);
md=min(md,tacke[gde].y);
K.push(gde);
stavio[gde]=svred;
}
}
for(int i=1;i<=L;i++){
int gde=tpoz-i;
if(gde>=1)
if(koji[gde]==0 and stavio[gde]<svred){
K.push(gde);
stavio[gde]=svred;
}
gde=tpoz+i;
if(gde<=L)
if(koji[gde]==0 and stavio[gde]<svred){
K.push(gde);
stavio[gde]=svred;
}
}
for(int i=0;i<graf[tren].size();i++){
if(koji[graf[tren][i]]!=0)
continue;
pp.gde=K.front();
pp.koji=graf[tren][i];
Q.push(pp);
K.pop();
}
}
return;
}
ofstream ouf;
void output(){
ouf.open(test+".out");
for(int i=1;i<=N;i++)
ouf<<tacke[pozicija[i]].id<<endl;
ouf.close();
return;
}
mt19937_64 rng;
int main(){
while(true){
int x1,x2,y11,y2;
cin>>x1>>y11>>x2>>y2;
cord a,b,c,d;
a.x=x1;
a.y=y11;
b.x=x2;
b.y=y2;
cin>>x1>>y11>>x2>>y2;
c.x=x1;
c.y=y11;
d.x=x2;
d.y=y2;
cout<<seku(a,b,c,d)<<endl;
}
rng.seed(time(NULL));
ios_base::sync_with_stdio(false);
cin.tie(0);
ifstream inf;
inf.open(test+".txt");
//#define cin inf
cin>>N>>M;
for(int i=1;i<=M;i++){
cin>>grane[i].a>>grane[i].b;
degree[grane[i].a]++;
degree[grane[i].b]++;
graf[grane[i].a].push_back(grane[i].b);
graf[grane[i].b].push_back(grane[i].a);
}
cin>>L;
for(int i=1;i<=L;i++){
cin>>tacke[i].x>>tacke[i].y;
tacke[i].id=i;
}
for(int i=1;i<=N;i++){
cin>>pozicija[i];
koji[pozicija[i]]=i;
}
cout<<prebroj()<<endl;
return 0;
for(int i=1;i<=N;i++)
sort(graf[i].begin(),graf[i].end(),podeg);
for(int i=1;i<=N;i++)
niz[i]=i;
sort(niz+1,niz+1+N,podeg);
msbacaj(1,L);
sort(tacke+1,tacke+1+L,pox);
for(int i=1;i<=N;i++){
pozicija[i]=V[i-1];
koji[V[i-1]]=i;
}
stavi();
int nov,gmax,res=prebroj();
gmax=res;
int a,b;
cout<<"SKOR JE "<<res<<endl;
while(true){
a=1;
b=2;
bool bolji=false;
for(int a=1;a<=L;a++)
for(int b=a+1;b<=L;b++){
//cout<<a<<" "<<b<<endl;
if(koji[a]==koji[b])
continue;
zameni(a,b);
nov=prebroj();
if(nov<res){
bolji=true;
if(nov<gmax){
cout<<"SKOR JE SADA "<<nov<<endl;
output();
gmax=nov;
}
res=nov;
continue;
}
zameni(a,b);
}
if(bolji==false){
for(int i=1;i<=N;i++){
int x=rng()%L+1;
while(koji[x]!=0)
x=rng()%L+1;
pozicija[i]=x;
koji[x]=i;
}
res=prebroj();
}
}
return 0;
}
Compilation message
pinball.cpp: In function 'void stavi()':
pinball.cpp:97:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
97 | if(koji[gde]==0 and tacke[gde].y>vl or tacke[gde].y<ml){
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
pinball.cpp:105:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
105 | if(koji[gde]==0 and tacke[gde].y>vd or tacke[gde].y<md){
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
pinball.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int i=0;i<graf[tren].size();i++){
| ~^~~~~~~~~~~~~~~~~~
pinball.cpp: In function 'int main()':
pinball.cpp:205:9: warning: variable 'a' set but not used [-Wunused-but-set-variable]
205 | int a,b;
| ^
pinball.cpp:205:11: warning: variable 'b' set but not used [-Wunused-but-set-variable]
205 | int a,b;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1072 ms |
1952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1072 ms |
1952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1072 ms |
1952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1072 ms |
1952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
