Problem A:
Check whether exist a pair i and j,they satisfy xi+di = xj && xj+dj = xi;

Problem B:
Pay attention to Just Right or Red. use Div and Mod can solve it easily;

Problem C:
As we know, there are only two path -- forward and reverse, so we can do DFS from the one-degree nodes (only two nodes).
As their index may be very larger, so I used map<int,int> to do hash.

void dfs(int i)
{
     int sz = mat[i].size()-1, j;
     UF(j,0,sz)
     if (!vis[mat[i][j]])
     {
        vis[mat[i][j]] = 1;
        printf(" %d",val[mat[i][j]]);
        dfs(mat[i][j]);
     }
}

Problem D:
Floyd.
First, Floyd pretreat the path from I to J, and save the path.
Then get the answer.
The order is a1,a2...ak, K is the number of the leaves, we can assume a0 = a_k+1 = 1, the root.
then, answer push_back the path[ai][a_i+1].

if the ans.size() > 2*N-1 , cout -1;
else cout the answer.

http://www.codeforces.com/contest/1/problem/C

the problem give us 3 points, and the  polygon is equilateral, so we can evaluate the loction of the polygon's center.
it's also the center of the triangle of  input <=> the center of its circumcircle.

we can evaluate the center point, and also the radius of its circumcircle.
If we know the 3 points, the radius is invariable. so, more points the polygon have, larger area the polygon will have.
Then we can enumerate the number of the polygon's points in ascending order.

The key to sovle Problem C is how you check the given number of points N is OK!

After know the center and radius, the triangle divide into three parts, then I use division to calculate the number of points in each part, What the result? I always got "wa" at test 6.

After WA many times, I think it must go awry in the division, so i used  method of superposition rather than division. In other words, I first calculate t[i] = A[i]/a, this got WA,  then I alter this by add a one by one. see it in function OK();



my code:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;
#define UF(i,a,b) for(i=(a);i<=(b);++i)
#define DF(i,b,a) for(i=(b);i>=(a);--i)

const double eps = 1e-6;
const double PI = acos(-1.0);

inline int sgn(double a)
{
       return (a > eps) - (a < -eps);
}
inline double sqr(double a)
{
       return a*a;
}
struct Point
{
       double x,y;
       void read() {
            scanf("%lf %lf",&x,&y);
       }          
}trg[3], rec[110], cir;
double ang[3], A[3], R;

inline double Dist(Point a, Point b)
{
       return sqrt(sqr(a.x-b.x) + sqr(b.y-a.y));
}
inline double xmul(Point a, Point b, Point c)
{
       return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
void OutCir(Point T[])   // calculate the center and radius, T[] is triangle
{
    double a, b, c, c1, c2, area;
    double xA, yA, xB, yB, xC, yC;
    area = fabs(xmul(T[0],T[1],T[2]))/2;   
    a = Dist(T[0], T[1]);
    b = Dist(T[1], T[2]);
    c = Dist(T[2], T[0]);
    R = a*b*c / (4*area);
   
    xA = T[0].x, yA = T[0].y;
    xB = T[1].x, yB = T[1].y;
    xC = T[2].x, yC = T[2].y;

    c1 = (xA*xA + yA*yA - xB*xB - yB*yB)/2;
    c2 = (xA*xA + yA*yA - xC*xC - yC*yC)/2;

    cir.x = ( c1*(yA-yC) - c2*(yA-yB) );
    cir.x /= ((xA-xB)*(yA-yC) - (xA-xC)*(yA-yB)); /*a*/
    cir.y = ( c1*(xA-xC) - c2*(xA - xB) );
    cir.y /= ((yA-yB)*(xA-xC) - (yA-yC)*(xA-xB));    /*b*/
}

void Sort()
{
     int i, j;
     UF(i,0,2)
     ang[i] = atan2(trg[i].y-cir.y, trg[i].x-cir.x);
     UF(i,0,2)
     UF(j,i+1,2)
     if (sgn(ang[i]-ang[j]) > 0)
     {
                 swap(trg[i], trg[j]);
                 swap(ang[i], ang[j]);
     }
     A[0] = ang[1] - ang[0];
     A[1] = ang[2] - ang[1];
     A[2] = 2*PI - A[0] - A[1];
}

int Ok(int n)
{
     double a = 2*PI / n, b = 0;
     int t[3] = {0}, i;
     UF(i,0,2)
     {
              b = 0.0;
              while (sgn(A[i]-b) > 0)
              {
                    t[i]++;
                    b += a;
              }
     }
     return (t[0] && t[1] && t[2] && t[0] + t[1] + t[2] == n);
}
int main()
{
    int i;
    UF(i,0,2) trg[i].read();
    OutCir(trg);
    Sort();
    UF(i,3,100)
    {
       if (Ok(i)) break;
    }   
    double area = 0;
    if (i > 100) i = 100;
    area = i * R * R * sin(2*PI/i) / 2.0;
    printf("%.8lf\n", area);
     return 0;
}

 

 

A: it's very easy. a bool vis[] is ok.

B: it can think as a directional Graph. xi->yi. there are two (a ,b), they appeer time less than N-1. we can do dfs from a to b, to check whether a can reach b, if it can, cout  a b , else cout b a.
ps:What a bad thing is I got WA during the contest, because I wrote  a 'j' as i. = =....

C: let change the sequence to a sequence only have -1,0, 1.
   s[1] = 0, if in[i]-in[i-1] > 0, s[i] = 1, else if less than 0, s[i] = -1, no change to oh.

First, we can know, if the shortest unordered subsequence exist, the length is 3, and the first number can be one of the three. scan S[i] from 2->N, if S[i]!=0, break,b=i, then continue scan, if exist S[i]+S[b]==0,break, c = i, then the ouordered subS exist.
sub is 0 1 -1 or 0 -1 1,


From -100 0 100 98 =>0 1 1 -1, but as the method above, a = 1, b = 2, c = 4, but they are ordered. the ans should be a, c-1, c. a is always 1.

why?   b is the first 1(-1), c is the first -1(1), so the number between b and c, is less than numb[b] && larger than numb[c] / larger than b && less than c, also may equal to numb[b] so compare "numb[c-1] to numb[a]" is the same "numb[b] to numb[a]" ,larger or less. numb[c] only compared to numb[c-1] from the S[]. so a c-1 c can be the ans.

/* my code:
val[1] = 0;
          scanf("%d",&a);
          for (i = 2; i <= N; i++)
          {
              scanf("%d",&b);
              val[i] = (b-a);
              a = b;
              if (val[i]<0) val[i] = -1;
              else if (val[i]>0) val[i] = 1;
          }
      //    if (N <= 2) {printf("0\n");continue ;}
         
          k = 1;
          a = 1;
         
          for (i = 2; i <= N; i++)
              if (val[i]) break;
         
          if (i <= N)
          {
             b = i;
             k++;
             for (i++; i <= N; i++)
             if (val[i]+val[b]==0)
                break;               
            
             if (i<=N)
             {
              k++;
              b = i-1;
              c = i;
             }
          }

*/

I was Hacked by others. After thinking problem E, I find the bug -100 0 100 98, but the contest is over.

This Round....How tragical I am !!!
I will do better the next Round.


I want to know how to solve the Problem D and Problem E, can you help me? thanks..