#include <iostream>
#include <cmath>
#include <random>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
int n;
int m;
int sen;
int cover[100];
int c[100];
int sen1;
struct Point{
double x,y;
} ;
Point initial[100];
int star[100];
Point current1[100];
Point best[100];
Point newsol[100];
Point finall[100];
Point target[100];
Point base;
Point current2[100];
Point m3;
int reach[100];
int b[100];
double rs;
int num;
double rc;
int k;
int num2;
int num3;
double initial_temperature;
double cooling_rate;
int max_iterations;
int canrun=1;
void equall(Point m1[], Point m2[])
{
for(int i=1;i<=n;i++)
{
m1[i].x=m2[i].x;
m1[i].y=m2[i].y;
}
}
double distance(Point m1,Point m2)
{
return sqrt(pow((m1.x-m2.x),2)+pow((m1.y-m2.y),2));
}
double randomReal(double a, double b) {
static std::random_device rd;
static std::mt19937 gen(rd());
std::uniform_real_distribution<double> dis(a, b);
return dis(gen);
}
int randomInteger(int n) {
static std::random_device rd;
static std::mt19937 gen(rd());
std::uniform_int_distribution<int> dis(1, n);
return dis(gen);
}
double arg(Point m)
{
double k= m.y/m.x;
double angle= atan(k);
double q= (M_PI+ angle);
if ((m.x==0)&&(m.y>=0)) return M_PI/2;
if ((m.x==0)&&(m.y<0)) return -(M_PI/2);
else if(m.x> 0) return angle;
else if(m.x < 0)
{
if (q> M_PI) q=q-2*M_PI;
}
return q;
}
int coverage(int j,Point sensor[])
{
int res=0;
if(j>0)
{
for(int i=1;i<=n;i++)
{
if (distance(target[j],sensor[i])<=rs) res++;
}
}
else if (j==0)
{
for(int i=1;i<=n;i++)
{
if (distance(target[j],sensor[i])<=rc) res++;
}
}
return res;
}
bool safe(int index,Point sensor[],int sen,int previousstate)
{
double dis2= distance(target[index],base);
double dis3= distance(target[star[previousstate]],target[index]);
double dis=dis2+dis3;
int state= reach[0];
int remain= k-state;
int remainsensor= n-sen;
int can3=ceil(dis2/rc)-1;
int can4=ceil(dis3/rc)-1;
int can=can3+can4+1;
int can1= remain*can;
if(remainsensor< can1) {return false;}
else{ return true;}
}
void quayvebase(int index, Point sensor[],int sen)
{
canrun=1;
// cout<<"QUAY VE BASE"<<endl;
if(index==0)
{
if(sen>n)
{
canrun=0;
}
else
{
sensor[sen].x=base.x;
sensor[sen].y=base.y;
//cout<<"SENSOR thu "<<sen<<" : "<<sensor[sen].x<<" "<<sensor[sen].y<<endl;
sen++;
}
}
else
{
double dis= distance(target[index],base);
Point m2;
m2.x= -target[index].x+base.x;
m2.y= -target[index].y+base.y;
double theta= arg(m2);
int state= coverage(0,sensor);
int remain= k-state;
int can=ceil(dis/rc)-1;
//cout<<"CAN "<<remain*can<<"SENSORS DE VE BASE."<<endl;
if((sen+can*remain)>n)
{
//cout<<"SAI: "<<sen+(can*remain)-1<<endl;
canrun=0;
}
else
{
sensor[sen].x= target[index].x;
sensor[sen].y=target[index].y;
sen++;
// cout<<"SENSOR thu "<<sen<<" "<<sensor[sen].x<<" "<<sensor[sen].y<<endl;
for(int i=1;i<=can;i++)
{
for(int j=sen;j<=sen+remain-1;j++)
{
sensor[j].x= target[index].x+i*rc*cos(theta);
sensor[j].y= target[index].y+i*rc*sin(theta);
// cout<<"SENSOR thu "<<j<<" "<<sensor[j].x<<" "<<sensor[j].y<<endl;
}
sen=sen+remain;
}
}
}
sen1=sen;
}
bool visited(int i,Point sensor[], double rs)
{
for( int j =1;j<=n;j++)
{
if(distance(sensor[j],target[i])<rs) return true;
}
return false;
}
void quet(Point sensor[],double rs)
{
//cout<<"Reach base: "<<reach[0]<<endl;
num=1;
for(int i=1;i<=m;i++)
{
//cout<<"reach:"<<i<<" la: "<<reach[i]<<endl;
if(reach[i]<k)
{
b[num]=i;
num++;
}
}
}
void quetsafe(int sen,Point sensor[],double rc, int previousstate)
{
num2=1;
for(int i=1;i<=num-1;i++)
{
if(safe(b[i],sensor,sen-1,previousstate)==true)
{
c[num2]=b[i];
num2++;
}
}
}
void direct(Point m, Point m1, double angle, double radios)
{
Point m2;
m2.x = m1.x - m.x;
m2.y = m1.y - m.y;
double theta = arg(m2);
double bisec = angle / 2;
double under = theta - bisec;
double upper = theta + bisec;
double phi = randomReal(under, upper);
double newDistance = randomReal(rs, radios); // Changed variable name
m3.x = m.x + newDistance * cos(phi); // Use newDistance here
m3.y = m.y + newDistance * sin(phi); // Use newDistance here
}
void khoitao(Point current[])
{
for(int i=1;i<=n;i++)
{
current[i].x=-1e9;
current[i].y=-1e9;
}
target[0].x=base.x;
target[0].y=base.y;
}
int objective_function(Point current[])
{
if(canrun==0) return 0;
else{
num3=1;
for(int i=1;i<=m;i++)
{
if((reach[i]>=k)&&(coverage(i,current))>=k) num3++;
}
return num3-1;
}
}
void nhay(Point current[])
{
for(int i=0;i<=m;i++) reach[i]=0;
khoitao(current);
int sen=1;
int state=1;
star[0]=0;
while(sen<=(n))
{
int i;
quet(current,rs);
if(reach[0]<k)
{
quetsafe(sen,current,rc,state-1);
if(num2==1)
{
reach[star[state-1]]++;
quayvebase(star[state-1],current,sen);
if(canrun==1)
{
reach[0]=k;
sen=sen1;
star[state]=0;
state++;
}
else if(canrun==0)
{
// cout<<"KHONG NHAY DC!";
sen=(n+1);
}
}
else if(num2>1)
{
i=randomInteger(num2-1);
if(c[i]==star[state-1])
{
if(num2>2)
{
if(i==(num2-1)) i=1;
else i++;
star[state]= c[i];
// cout<<"NHAY TU "<<star[state-1]<<" DEN "<<star[state]<<endl;
reach[star[state-1]]++;
int temp= coverage(star[state],current);
// cout<<"TEMP CUA TARGET "<<star[state]<<" : "<<temp<<endl;
Point m2;
Point m;
Point m1;
m.x=target[star[state-1]].x;
m.y=target[star[state-1]].y;
m1.x=target[star[state]].x;
m1.y=target[star[state]].y;
m2.x = m1.x - m.x;
m2.y = m1.y - m.y;
double theta = arg(m2);
double bisec = (M_PI/4)/2;
double under = theta - bisec;
double upper = theta + bisec;
double phi = randomReal(under, upper);
double newDistance = rs;
m3.x = m.x + newDistance * cos(phi);
m3.y = m.y + newDistance * sin(phi);
current[sen].x=m3.x;
current[sen].y=m3.y;
sen++;
int sen0=sen;
for(int i=sen0;i<=n;i++)
{
if(coverage(star[state],current)>temp)
{
//cout<<"COVER MOI: "<<coverage(star[state],current)<<endl;
reach[star[state]]++;
break;
}
else{
Point m2;
Point m;
Point m1;
m.x=current[i-1].x;
m.y=current[i-1].y;
m1.x=target[star[state]].x;
m1.y=target[star[state]].y;
m2.x = m1.x - m.x;
m2.y = m1.y - m.y;
double theta = arg(m2);
double bisec = (M_PI/4)/2;
double under = theta - bisec;
double upper = theta + bisec;
double phi = randomReal(under, upper);
double newDistance = randomReal(rs, rc);
m3.x = m.x + newDistance * cos(phi);
m3.y = m.y + newDistance * sin(phi);
current[i].x=m3.x;
current[i].y=m3.y;
sen=i+1;
if(sen==(n+1)) break;
}
}
state++;
for(int j=sen0-1;j<=sen-1;j++)
{
// cout<<"SENSOR thu "<<j<<" "<<current[j].x<< " "<<current[j].y<<endl;
}
}
else if(num2==2)
{
reach[star[state-1]]++;
quayvebase(star[state-1],current,sen);
if(canrun==1)
{
reach[0]=k;
sen=sen1;
star[state]=0;
state++;
}
else if(canrun==0)
{
// cout<<"KHONG NHAY DC!";
sen=(n+1);
}
}
}
else
{
star[state]= c[i];
// cout<<"NHAY TU "<<star[state-1]<<" DEN "<<star[state]<<endl;
reach[star[state-1]]++;
int temp= coverage(star[state],current);
// cout<<"TEMP CUA TARGET "<<star[state]<<" : "<<temp<<endl;
Point m2;
Point m;
Point m1;
m.x=target[star[state-1]].x;
m.y=target[star[state-1]].y;
m1.x=target[star[state]].x;
m1.y=target[star[state]].y;
m2.x = m1.x - m.x;
m2.y = m1.y - m.y;
double theta = arg(m2);
double bisec = (M_PI/4)/2;
double under = theta - bisec;
double upper = theta + bisec;
double phi = randomReal(under, upper);
double newDistance = rs;
m3.x = m.x + newDistance * cos(phi);
m3.y = m.y + newDistance * sin(phi);
current[sen].x=m3.x;
current[sen].y=m3.y;
sen++;
int sen0=sen;
for(int i=sen0;i<=n;i++)
{
if(coverage(star[state],current)>temp)
{
// cout<<"COVER MOI: "<<coverage(star[state],current)<<endl;
reach[star[state]]++;
break;
}
else{
Point m2;
Point m;
Point m1;
m.x=current[i-1].x;
m.y=current[i-1].y;
m1.x=target[star[state]].x;
m1.y=target[star[state]].y;
m2.x = m1.x - m.x;
m2.y = m1.y - m.y;
double theta = arg(m2);
double bisec = (M_PI/4)/2;
double under = theta - bisec;
double upper = theta + bisec;
double phi = randomReal(under, upper);
double newDistance = randomReal(rs, rc);
m3.x = m.x + newDistance * cos(phi);
m3.y = m.y + newDistance * sin(phi);
current[i].x=m3.x;
current[i].y=m3.y;
sen=i+1;
if(sen==(n+1)) break;
}
}
state++;
for(int j=sen0-1;j<=sen-1;j++)
{
// cout<<"SENSOR thu "<<j<<" "<<current[j].x<< " "<<current[j].y<<endl;
}
}
}
}
else{
if(num==1)
{
reach[star[state-1]]++;
quayvebase(star[state-1],current,sen);
if(canrun==1)
{
reach[0]=k;
sen=sen1;
star[state]=0;
state++;
}
else if(canrun==0)
{
// cout<<"KHONG NHAY DC!";
sen=(n+1);
}
}
else if(num>1)
{
i=randomInteger(num-1);
if(b[i]==star[state-1])
{
if(num>2)
{
if(i==(num-1)) i=1;
else i++;
star[state]= b[i];
// cout<<"NHAY TU "<<star[state-1]<<" DEN "<<star[state]<<endl;
reach[star[state-1]]++;
int temp= coverage(star[state],current);
// cout<<"TEMP CUA TARGET "<<star[state]<<" : "<<temp<<endl;
Point m2;
Point m;
Point m1;
m.x=target[star[state-1]].x;
m.y=target[star[state-1]].y;
m1.x=target[star[state]].x;
m1.y=target[star[state]].y;
m2.x = m1.x - m.x;
m2.y = m1.y - m.y;
double theta = arg(m2);
double bisec = (M_PI/4)/2;
double under = theta - bisec;
double upper = theta + bisec;
double phi = randomReal(under, upper);
double newDistance = rs;
m3.x = m.x + newDistance * cos(phi);
m3.y = m.y + newDistance * sin(phi);
current[sen].x=m3.x;
current[sen].y=m3.y;
sen++;
int sen0=sen;
for(int i=sen0;i<=n;i++)
{
if(coverage(star[state],current)>temp)
{
// cout<<"COVER MOI: "<<coverage(star[state],current)<<endl;
reach[star[state]]++;
break;
}
else{
Point m2;
Point m;
Point m1;
m.x=current[i-1].x;
m.y=current[i-1].y;
m1.x=target[star[state]].x;
m1.y=target[star[state]].y;
m2.x = m1.x - m.x;
m2.y = m1.y - m.y;
double theta = arg(m2);
double bisec = (M_PI/4)/2;
double under = theta - bisec;
double upper = theta + bisec;
double phi = randomReal(under, upper);
double newDistance = randomReal(rs, rc);
m3.x = m.x + newDistance * cos(phi);
m3.y = m.y + newDistance * sin(phi);
current[i].x=m3.x;
current[i].y=m3.y;
sen=i+1;
if(sen==(n+1)) break;
}
}
state++;
for(int j=sen0-1;j<=sen-1;j++)
{
// cout<<"SENSOR thu "<<j<<" "<<current[j].x<< " "<<current[j].y<<endl;
}
}
else if(num==2)
{
reach[star[state-1]]++;
quayvebase(star[state-1],current,sen);
if(canrun==1)
{
reach[0]=k;
sen=sen1;
star[state]=0;
state++;
}
else if(canrun==0)
{
// cout<<"KHONG NHAY DC!";
sen=(n+1);
}
}
}
else
{
star[state]= b[i];
// cout<<"..NHAY TU "<<star[state-1]<<" DEN "<<star[state]<<endl;
reach[star[state-1]]++;
int temp= coverage(star[state],current);
// cout<<"TEMP CUA TARGET "<<star[state]<<" : "<<temp<<endl;
Point m2;
Point m;
Point m1;
m.x=target[star[state-1]].x;
m.y=target[star[state-1]].y;
m1.x=target[star[state]].x;
m1.y=target[star[state]].y;
m2.x = m1.x - m.x;
m2.y = m1.y - m.y;
double theta = arg(m2);
double bisec = (M_PI/4)/2;
double under = theta - bisec;
double upper = theta + bisec;
double phi = randomReal(under, upper);
double newDistance = rs;
m3.x = m.x + newDistance * cos(phi);
m3.y = m.y + newDistance * sin(phi);
current[sen].x=m3.x;
current[sen].y=m3.y;
sen++;
int sen0=sen;
for(int i=sen0;i<=n;i++)
{
if(coverage(star[state],current)>temp)
{
// cout<<"COVER MOI: "<<coverage(star[state],current)<<endl;
reach[star[state]]++;
break;
}
else{
Point m2;
Point m;
Point m1;
m.x=current[i-1].x;
m.y=current[i-1].y;
m1.x=target[star[state]].x;
m1.y=target[star[state]].y;
m2.x = m1.x - m.x;
m2.y = m1.y - m.y;
double theta = arg(m2);
double bisec = (M_PI/4)/2;
double under = theta - bisec;
double upper = theta + bisec;
double phi = randomReal(under, upper);
double newDistance = randomReal(rs, rc);
m3.x = m.x + newDistance * cos(phi);
m3.y = m.y + newDistance * sin(phi);
current[i].x=m3.x;
current[i].y=m3.y;
sen=i+1;
if(sen==(n+1)) break;
}
}
state++;
for(int j=sen0-1;j<=sen-1;j++)
{
// cout<<"SENSOR thu "<<j<<" "<<current[j].x<< " "<<current[j].y<<endl;
}
}
}
}
}
quet(current,rs);
//cout<<"SEN DANG LA: "<<sen<<endl;
equall(current2,current);
// cout<<"GIA TRI: ";
// cout<<objective_function(current)<<endl;
khoitao(current);
}
void SA()
{
khoitao(initial);
equall(current1,initial);
double current_temperature = initial_temperature;
equall(best,current1);
double best_value = objective_function(current1);
for (int i = 0; i < max_iterations; ++i) {
double fcurrent= objective_function(current1);
nhay(current1);
equall(newsol,current2);
double new_value = objective_function(newsol);
if (new_value > best_value) {
equall(best,newsol);
equall(current1,newsol);
best_value = new_value;
}
double delta = new_value - fcurrent;
if (delta > 0 || ((double)rand() / RAND_MAX) < exp(delta / current_temperature)) {
equall(current1,newsol);
}
current_temperature *= cooling_rate;
}
cout << "Best objective function value: " << best_value << endl;
equall(finall,best);
}
void input()
{
cout<<"NHAP SO LUONG TARGET: ";
cin>>m;
for(int i=1;i<=m;i++)
{
cout<<"NHAP TOA DO TARGET "<<i<<" : ";
cin>>target[i].x>>target[i].y;
}
cout<<"NHAP TOA DO BASE: ";
cin>>base.x>>base.y;
cout<<"NHAP SO LUONG SENSOR: ";
cin>>n;
cout<<"NHAP BAN KINH CAM BIEN: ";
cin>>rs;
cout<<"NHAP BAN KINH TRUYEN TIN: ";
cin>>rc;
cout<<"NHAP SO K: ";
cin>>k;
}
int main()
{
initial_temperature = 1000;
cooling_rate = 0.99;
max_iterations = 10000;
input();
SA();
for(int i=1;i<=n;i++)
{
cout<<"SENSOR THU "<<i<<" : "<<finall[i].x<<" "<<finall[i].y<<endl;
}
for(int i=1;i<=m;i++)
{
cout<<"DO COVERAGE CUA TARGET "<<i<<" : "<<coverage(i,finall)<<endl;
}
// for(int i= 1;i<=40;i++)
//{
// cout<<"NHAY LAN : "<<i<<endl;
//khoitao(current1);
//star[1]=2;
//cout<<"SAFE KHI NHAY TU 2 TOI 3: "<<safe(3,current1,8,1);
//nhay(current1);
//}
//}
// cout<<" COVERAGE CUA BASE: "<<coverage(0,current)<<endl;
//quayvebase(1,current,1);
// for(int i=1;i<7;i++)
//{
// cout<<"NHAY LAN: "<<i<<endl;
//nhay(current1);
//} //cout<<safe(2,current,6)<<endl;
//for(int i=1;i<=7;i++) cout<< randomInteger(0)<<endl;
}