ens-ulm-1

commit 6708cd26b3ca2478bef78a2227a1a69e42e7c45b
parent fbe95e78447eab3458619d57f0feb1c726c2f8a9
Author: Jachiet Louis <louis@jachiet.com>
Date:   Sat,  5 Apr 2014 14:24:21 +0200

Merge branch 'master' of gitorious.org:ens-ulm-1/ens-ulm-1

Diffstat:
contest/mc/lecture.cpp
 | 
66
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------

1 file changed, 59 insertions(+), 7 deletions(-)
diff --git a/contest/mc/lecture.cpp b/contest/mc/lecture.cpp
@@ -3,7 +3,8 @@
 #include <map>
 #include <algorithm>
 #include <cstdio>
-#include <string.h>
+#include <cstring>
+#include <cmath>
 
 #define N_SOMMETS_MAJ 12000
 #define N_ARETES_MAJ 18000
@@ -16,8 +17,10 @@ using namespace std;
  int n_vehicules;
  int s_depart;
 
-double longitudes[N_SOMMETS_MAJ];
-double latitudes[N_SOMMETS_MAJ];
+double longitude_min, longitude_max;
+double latitude_min, latitude_max;
+double longitude[N_SOMMETS_MAJ];
+double latitude[N_SOMMETS_MAJ];
 
 // caracteristiques d'une arete
 int depart[N_ARETES_MAJ];//depart
@@ -30,6 +33,8 @@ vector<vector<int> > adj(N_SOMMETS_MAJ); // matrice d'adjacence
 
 map<pair<int, int>, int> id_arete;
 
+vector<int> _solution[8];
+
 void affiche_sortie(vector<int> trajectoires[]) {
   printf("%d\n", n_vehicules);
   for (int i=0; i< n_vehicules; i++) {
@@ -40,6 +45,7 @@ void affiche_sortie(vector<int> trajectoires[]) {
   }
 }
 
+// (temps_tronques)
 // format: score, temps1, temps2, ..., temps8
 // (ou vide si solution invalide)
 vector<int> evalue_solution(vector<int> trajectoires[]) {
@@ -51,18 +57,23 @@ vector<int> evalue_solution(vector<int> trajectoires[]) {
   int score = 0;
   for (int i=0; i< n_vehicules; i++) {
     int temps = 0;
-    for (int j=0; j< trajectoires[i].size() - 1; j++) {
+    for (int j=0; j< int(trajectoires[i].size() - 1); j++) {
       pair<int, int> p = make_pair(trajectoires[i][j], trajectoires[i][j+1]);
       int a = id_arete[p];
       if (!a) {
         resultat.clear();
         return resultat;
       }
+      temps += cout[a];
+      if (temps > max_limit) {
+        // undo
+        temps -= cout[a];
+        break;
+      }
       if (!aretes[a]) {
         score += longueur[a];
         aretes[a] = 1;
       }
-      temps += cout[a];
     }
     resultat.push_back(temps);
   }
@@ -80,7 +91,7 @@ int score_solution(vector<int> trajectoires[]) {
 int tronque_solution(vector<int> trajectoires[], int max_limit) {
   for (int i=0; i< n_vehicules; i++) {
     int temps = 0;
-    for (int j=0; j< trajectoires[i].size() - 1; j++) {
+    for (int j=0; j< int(trajectoires[i].size() - 1); j++) {
       pair<int, int> p = make_pair(trajectoires[i][j], trajectoires[i][j+1]);
       int a = id_arete[p];
       if (!a) {
@@ -104,7 +115,13 @@ void lecture_entree(){
   scanf("%d",&t_autorise);
   scanf("%d",&n_vehicules);
   scanf("%d",&s_depart);
-  for(int i=0;i<n_sommets;i++)scanf("%lf %lf",&longitudes[i],&latitudes[i]);
+  for(int i=0;i<n_sommets;i++) {
+    scanf("%lf %lf",&longitude[i],&latitude[i]);
+  }
+  longitude_min = *min_element(longitude, longitude + n_sommets);
+  longitude_max = *max_element(longitude, longitude + n_sommets);
+  latitude_min = *min_element(latitude, latitude + n_sommets);
+  latitude_max = *max_element(latitude, latitude + n_sommets);
   for(int i=1;i<=n_aretes;i++){
     int x;
     scanf("%d %d %d %d %d",&depart[i],&arrivee[i],&x,&cout[i],&longueur[i]);
@@ -118,7 +135,42 @@ void lecture_entree(){
   }
 }
 
+int plus_proche(double x, double y) {
+
+  int iBest = 0;
+  double best = hypot(x - longitude[0], y - latitude[0]);
+
+  for (int i = 1; i < n_sommets; i++) {
+    double cur = hypot(x - longitude[i], y - latitude[i]);
+    if (cur < best) {
+      best = cur;
+      iBest = i;
+    }
+  }
+
+  return iBest;
+}
+
+int plus_proche_norm(double dx, double dy) {
+
+  return plus_proche(longitude_min + dx * (longitude_max - longitude_min),
+                     latitude_min + dy * (latitude_max - latitude_min));
+
+}
+
+void init_solution(vector<int> sol[]) {
 
+  for (int i = 0; i < n_vehicules; i++)
+    sol[i].push_back(s_depart);
+
+}
+
+void goto_etoile(vector<int> sol[]) {
+
+  for (int i = 0; i < n_vehicules; i++)
+    sol[i].push_back(plus_proche_norm(.5 * (1+cos(2*M_PI/n_vehicules)), .5 * (1+sin(2*M_PI/n_vehicules))));
+
+}
 
 // 
 // int main(){