onlyone's blog

By onlyone, 9 years ago, In English,

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;
}

 


 

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Cool =)