 /**//*
给出一些平行于axes或与坐标轴成45°的线段
问其中有多少个三角形
n <= 50 (x,y) ∈ [-100,100]
不会做,一点想法都没有 哎
解题报告 http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm239
规模比较小,直接枚举三条边
但有个问题就是有些边可以连接起来,需要再处理

范围比较小,可以放大两倍(处理对角线交点),然后进行标记,看哪些边是有线段的
mark[x,y,d] 表示点(x,y)在方向d的单位长度上有线段覆盖
这种记录方法很好!!!
pLen[x,y,d]表示点(x,y)在方向d能延伸多长
有了以上的预处理后
统计时,枚举点(x,y),方向d,还有长度len(由于题目的三角形都是等腰的,所以枚举长度即可)
对于(x,y,d),另外一条直角边就行(x,y,d+2),斜边为(x,y,d+3)
长度要判断一下,跟角度有关
解题报告的代码写得真好!!
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>

using namespace std;

const int MAXN = 400;

 int dx[] = {1,1,0,-1,-1,-1,0,1};
 int dy[] = {0,1,1,1,0,-1,-1,-1};

bool mark[MAXN+1][MAXN+1][8];
int pLen[MAXN+1][MAXN+1][8];

 class HiddenTriangles {
public:

 int sign(int x) {∈
return x < 0 ? -1 : x > 0 ;
}
 void markIt(int x1,int y1,int x2,int y2) {
int d = 0;
while(dx[d] != sign(x2-x1) || dy[d] != sign(y2-y1))d++;
 while(x1!=x2 || y1!=y2) {// x1 = x2 && y1 = y2 , then break
mark[x1][y1][d] = true;
x1 += dx[d];
y1 += dy[d];
mark[x1][y1][(d+4)%8] = true;
}
}

 int calLen(int x ,int y , int d) {
 if(pLen[x][y][d] == -1) {
if(mark[x][y][d])pLen[x][y][d] = 1 + calLen(x+dx[d],y+dy[d],d);
else pLen[x][y][d] = 0;
}
return pLen[x][y][d];
}

 void calLen() {
memset(pLen , -1 , sizeof pLen);
for(int x = 0 ; x <= MAXN ; x++)
for(int y = 0 ; y <= MAXN ; y++)
for(int d = 0 ; d < 8 ; d++)
pLen[x][y][d] = calLen(x,y,d);
}
 int count() {
int ans = 0;
for(int x = 0 ; x <= MAXN ; x ++)
for(int y = 0 ; y <= MAXN ; y++)
 for(int d = 0 ; d < 8 ; d++) {
 for(int len = 1 ;;len++) {
if(pLen[x][y][d] < len || pLen[x][y][(d+2)%8] < len)break;
int side = d % 2 == 0 ? 1 : 2; // parallel to axes : form a 45 degree angle
if(pLen[x+dx[d]*len][y+dy[d]*len][(d+3)%8] >= len*side)ans++;
}
}
return ans;
}

 int howMany(vector <int> X1, vector <int> Y1, vector <int> X2, vector <int> Y2) {
memset(mark,false,sizeof mark);
int n = X1.size();
 for(int i = 0 ; i < n ; i++) {
markIt(2*X1[i]+200,2*Y1[i]+200,2*X2[i]+200,2*Y2[i]+200);//extend it
}
calLen();
return count();
}

};

|