uva 11529 Strange Tax Calculation （几何+计数）

时间：2021-03-08 14:39:59

题目链接： http://vjudge.net/problem/viewProblem.action?id=18277

这题暴力n^4妥妥的TLE！即使n^3也可能会T

正确的姿势应该是：枚举每个点作为三角形内（或外）的点，按对此点的极角排序，然后从某个点Aj开始，找到从它开始刚好转了超过180度的点，则j点Aj与此间转过的任何两个点组成的三角形都应该不包括中心点。

这样做可能是n^3的复杂度，但如果Aj做完后，Aj+1可以从上一次转过180度的点开始转，这样不就相当于n^2了uva 11529 Strange Tax Calculation （几何+计数）

#include <stdio.h>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <cmath>

using namespace std;

#define lson o<<1

#define rson o<<1|1

#define max(a,b) (a)>(b)?(a):(b)

#define min(a,b) (a)<(b)?(a):(b)

#define INF 200000000

#define pi acos(-1.0)

#define eps 1e-9

typedef long long ll;

double x[],y[];

double ang[*];

int main(){

//freopen("s.in","r",stdin);freopen("s.out","w",stdout);

   int n,cs=;

   while(scanf("%d",&n) && n){

      int i;

      double ans=,s,c;

      s=(double)(n-)*(n-)*(n-)/6.0;

      c=(double)n*(n-)*(n-)/6.0;

      for(i=;i<n;i++)scanf("%lf%lf",&x[i],&y[i]);

      if(n<){

        printf("City %d: 0.00\n",cs);

        continue;

      }

      for(i=;i<n;i++){

         int j,k;

         for(j=,k=;j<n;j++)if(i!=j){

                 ang[k]=atan2(y[j]-y[i],x[j]-x[i]);

                 if(ang[k]<eps)ang[k]+=*pi;

                 k++;

         }

         sort(ang,ang+n-);

         for(j=k;j<*k;j++)ang[j]=ang[j-k]+*pi;

         double temp=;int pos=;

         for(j=;j<k;j++){

            while(pos<=*k&&ang[pos]-ang[j]<pi)pos++;

            if(pos-j>)temp+=(pos-j-)*(pos-j-)/2.0;

         }

         ans+=(s-temp)/c;

      }

      printf("City %d: %.2lf\n",cs,ans);

      cs++;

   }

   return ;

}

772ms Accepted~

相关文章