691 - Triangle Partition

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

691 - Triangle Partition

Post by SilVer DirectXer »

Oh, i got a TLE.... :o
but i have already tried my best to reduce the running time.
[cpp]
#include <stdio.h>
#include <iostream.h>
#include <math.h>
class pt{
public:
long double X;
long double Y;
};

long double interval=0.01;
int num_of_data,AOC=0,AOB=0,BOC=0,num;
pt node[300],O;
int answer(long double interval);
void find_O(long double rad1,long double rad2);
void count_pt(pt O);
int test_on_point(long double interval);
int test_on_intersection(long double interval);
int eq1_eq2(int base);
int eq1_eq3(int base);
int eq2_eq3(int base);
void main(void)
{
int i,finished;
while(1)
{
cin>>num_of_data;
num=num_of_data+3-(num_of_data % 3)-3*(num_of_data %3==0);
if (num_of_data==0)
break;
for (i=0;i<num_of_data;i++)
cin>>node.X>>node.Y;
finished=test_on_point(interval);
if (finished==1)
{
printf("%.7lf %.7lf\n",O.X,O.Y);
continue;
}

finished=test_on_intersection(interval);
if (finished==1)
{
printf("%.7lf %.7lf\n",O.X,O.Y);
continue;
}
while(1)
{
finished=answer(interval);
if (finished==1)
{
printf("%.7lf %.7lf\n",O.X,O.Y);
break;
}
interval/=10;
}
}

}

void count_pt(pt O)
{
int i,temp;
long double OC,OA,OB,slopeA,slopeB,intslopeA,intslopeB;
AOB=0;BOC=0;AOC=0;
for (i=0;i<num_of_data;i++)
{
OA=node.Y-((long double)(O.Y)/(long double)(O.X))*node.X;
OB=node.Y-((long double)(O.Y*(node.X-1000))/(long double)(O.X-1000));
OC=node.Y-((long double)((O.Y-1000)*node.X)/(long double)(O.X))-1000;
slopeA=node.Y/(long double)node.X;
slopeB=node[i].Y/(long double)(node[i].X-1000);
intslopeA=O.Y/(long double)O.X;
intslopeB=O.Y/(long double)(O.X-1000);

if((OA<0.00005)&&(OB<0.00005)&&(OC<0.00005)&&(OA>-0.00005)&&(OB>-0.00005)&&(OC>-0.00005))
{
AOC++;
AOB++;
BOC++;
}
else
{
temp=0;
if((OA<0.00005)&&(slopeB>=intslopeB)&&(OA>-0.00005))
{
AOC++;
AOB++;
temp=1;
}
if((OB<0.00005)&&(slopeA<=intslopeA)&&(OB>-0.00005))
{
AOB++;
BOC++;
temp=1;
}
if((OC<0.00005)&&(slopeA>=intslopeA)&&(OC>-0.00005))
{
BOC++;
AOC++;
temp=1;
}
if((OA>0.00005)&&(OC<0.00005)&&(temp==0))
AOC++;
if((OA<0.00005)&&(OB<0.00005)&&(temp==0))
AOB++;
if((OC>0.00005)&&(OB>0.00005)&&(temp==0))
BOC++;
}
}

}

int answer(long double interval)
{
long double i,j,minA=0,maxA=0,minB=0,maxB=0,A=0,B=0,angle1=0,angle2=0;
int k;
maxB=0;minB=1;maxA=0;minA=2;
for (k=0;k<num_of_data;k++)
{
angle1=node[k].Y/(long double)node[k].X;
angle2=node[k].Y/(long double)((node[k].X)-1000);
A=(atan(angle1));
B=((-1)*atan(angle2));
B=0.785398163-B;
if (A>maxA)
maxA=A;
if (A<minA)
minA=A;
if (B>maxB)
maxB=B;
if (B<minB)
minB=B;
}
for (i=(minB-interval);i<(maxB+interval);i+=interval)
{
for (j=(minA-interval);j<(maxA+interval);j+=interval)
{
find_O(i,j);
count_pt(O);

if (AOB>=num/3 && AOC>=num/3 && BOC>=num/3)
{
return 1;
}
}
}
return 0;
}

void find_O(long double rad2,long double rad1)
{
long double slope1,slope2;
rad2+=2.35619449;

slope1=(long double)tan(rad1);
slope2=(long double)tan(rad2);

O.X=(1000)*(slope2)*(-1)/(long double)(slope1-slope2);
O.Y=slope1*O.X;

}

int test_on_point(long double interval)
{
int i;
for( i=0;i<num_of_data;i++)
{
O.X=node[i].X;
O.Y=node[i].Y;

count_pt(O);

if (AOB>=num/3 && AOC>=num/3 && BOC>=num/3)
{
return 1;
}
}
return 0;
}
int test_on_intersection(long double interval)
{
int i,right=0;

for(i=0;i<num_of_data;i++)
{
right=eq1_eq2(i); //get O
if (right==1)
return 1;
}

for(i=0;i<num_of_data;i++)
{
right=eq1_eq3(i); //get O
if (right==1)
return 1;

}


for(i=0;i<num_of_data;i++)
{
right=eq2_eq3(i); //get O
if (right==1)
return 1;
}
return 0;
}

int eq1_eq2(int base)
{
int i;
for (i=0;i<num_of_data;i++)
{
if (base==i)
continue;

O.X=(node[base].Y-1000)/(long double)node[base].X;
O.X-=node[i].Y/(long double)node[i].X;
O.X=(-1)*1000/(long double)O.X;
O.Y=node[i].Y*O.X/(long double)node[i].X;

count_pt(O);
if (AOB>=num/3 && AOC>=num/3 && BOC>=num/3)
{
return 1;
}
}
return 0;
}

int eq1_eq3(int base)
{
long double temp;
int i;
for (i=0;i<num_of_data;i++)
{
if (base==i)
continue;

O.X=(node[base].Y-1000)/(long double)node[base].X;
O.X+=node[i].Y/(long double)node[i].X;
temp=1000*(node[i].Y/(long double)node[i].X)-1000;
O.X=temp/(long double)O.X;
O.Y=(-1)*node[i].Y/(long double)node[i].X;
O.Y*=O.X-1000;

count_pt(O);
if (AOB>=num/3 && AOC>=num/3 && BOC>=num/3)
{
return 1;
}
}
return 0;
}

int eq2_eq3(int base)
{
int i;
for (i=0;i<num_of_data;i++)
{
if (base==i)
continue;

O.X=node[i].X-1000;
O.X*=node[base].Y/(long double)node[base].X;
O.X-=node[i].Y;
O.X=(-1)*1000*node[i].Y/O.X;
O.Y=node[base].Y*O.X/(long double)node[base].X;

count_pt(O);
if (AOB>=num/3 && AOC>=num/3 && BOC>=num/3)
{
return 1;
}
}
return 0;
}
[/cpp]

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum »

I am using similar algorithms to you only I get either WA or TLE. If I don't find the point from looking at points and lines then I think my code is a little better than yours, you seem to be scanning large areas finer and finer ? Instead I take the approach of deciding on a centre point and moving it away from the triangles sides by a distance d when the count for that sides inner triangle is too low. I reduce the distance d after a few moves each time. Unfortunately it is not working :(

So has anyone any better ideas for this problem ?

SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

Post by SilVer DirectXer »

yes, you are right.....

I am busy right now.
If i have time.
Let me write a "random algorithm", which randomly generate points and test if it satisify the conditions.

Lol~~

Post Reply

Return to “Volume 6 (600-699)”