TIOJ 1205 直角三角形

    第一次寫極角排序,用了一些不是很尋常的方法,然後就變成topcoder了
先講講這題的做法吧,首先很明顯枚舉可以做到n^3,
但是這個複雜度我們不是很滿意(其實寫得好,n^3可以過,因為時間限制7秒),
所以想到了一個方法,枚舉是直角的那個點,每次枚舉都做極角排序,
然後用爬行法找出所有以該點為直角的所有三角形,
這樣就可以很健康的1秒內通過

以下有很多其他細節
1.內積外積的等等操作,就不多贅述
2.我的極角排序方法是,先偵測它是否>=π,若是其中一個>=π,而另一個沒有
   就可以直接判斷它的大小,而若是都有或都沒有,就可以保證兩角相差<π,
   這時再用外積比較即可
3.爬行的部分是最容易寫錯的,我就de了好久的bug
   首先我們用p1和p2指向兩個點,比較 p2的角度 和 p1的角度+π/2
   若是前者大(相差超過π/2),那就 p1++
   若是後者大(相差小於π/2),那就 p2++
   而若是相同,那麼答案就可以++,並繼續找下一個p2
   不過有兩點要注意:
   就是p2不能繞一圈之後超過p1 否則會重複計算 所以才有以下 if(p2>=p1+si)break;
   再來是判斷 p2的角度 大於 p1的角度+π/2 的方法 是內積和外積都要>=0
   不是只有內積喔(否則若是差距超過 3/2π 的也會被判定成在π/2內)
   而剩下判斷相差是否在π/2內就只要內積<0即可
   相差剛好是π/2就是內積為0 這不用多說

   以下就是我的code

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> vec;
vec operator+(vec k,vec l){
return {k.X+l.X,k.Y+l.Y};
}
vec operator-(vec k,vec l){
return {k.X-l.X,k.Y-l.Y};
}
ll operator*(vec k,vec l){
return k.X*l.X+k.Y*l.Y;
}
ll operator^(vec k,vec l){
return k.X*l.Y-k.Y*l.X;
}
ll n,x,y;
vec po[1510];
bool cmp(vec a,vec b){
if((a.Y>0||(a.Y==0&&a.X>0))&&(b.Y<0||(b.Y==0&&b.X<0)))
return 1;
if((b.Y>0||(b.Y==0&&b.X>0))&&(a.Y<0||(a.Y==0&&a.X<0)))
return 0;
return (a^b)>0;
}
int dec(int now){
x=po[now].X; y=po[now].Y;
vec *arr=new vec[3010];
int p=0;
int si=n-1;
for(int i=0;i<n;i++){
if(i==now)
continue;
arr[p++]=po[i]-po[now];
}
sort(arr,arr+si,cmp);
for(int i=0;i<si;i++)
arr[i+si]=arr[i];

int p1=0,p2=1;
int ans=0;
while(p1<si){

if(((arr[p1])*(arr[p2]))<0||((arr[p1])^(arr[p2]))<0){
p1++;
continue;
}
if(((arr[p1])*(arr[p2]))>0){
p2++; if(p2>=p1+si) break;
continue;
}
int nu=0;
while(((arr[p1])*(arr[p2]))==0&&((arr[p1])^(arr[p2]))>=0){
nu++;
p2++;
if(p2>=p1+si)
break;
}
ans+=nu;
p2-=nu;
p1++;
}
delete arr;
return ans;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
while(cin>>n){
if(!n)
return 0;
int ans=0;
for(int i=0;i<n;i++)
cin>>po[i].X>>po[i].Y;
for(int i=0;i<n;i++)
ans+=dec(i);
cout<<ans<<'\n';
}
}