Kupas Kode: tokilearning

Update 2017-06-14:
Web tokilearning yang lama sudah tidak aktif, Anda sudah tidak bisa mengumpulkan jawaban untuk soal ini. Namun Anda masih dapat mempelajarinya di tulisan ini.

Oke kali ini saya akan membahas soal Webs dari tokilearning. Konon katanya soal ini digunakan untuk simulasi Pelatnas 2 TOKI 2010 di UGM. Dari gaya bahasanya, kelihatannya soal ini dibuat oleh Irvan Jahja. Sekilas, soal ini tampak menyeramkan. Pada kenyataannya tidak terlalu menyeramkan, asal kita memilah-milah dan tahu apa yang harus dikerjakan.

Tugas kita adalah menghitung berapa banyak segitiga yang ada!

Biasanya, soal geometri seperti ini erat hubungannya dengan graf. Hmm coba perhatikan, seandainya titik perpotongan dari dua benang kita anggap sebagai node, lalu benang yang menghubungkan antar dua titik perpotongan sebagai edge, maka kita dapatkan sebuah graf yang planar.

Berapa banyak node maksimumnya? Persoalan berapa banyaknya node ini serupa dengan persoalan berikut:

Diberikan sebuah kue berbentuk persegi. Dengan N kali pemotongan, berapa banyaknya potongan maksimum yang bisa dihasilkan?

Jawab:
Misalkan sudah dilakukan X-1 kali pemotongan di kue tersebut dan banyaknya potongan yang dihasilkan sejauh ini adalah optimal (sebanyak mungkin). Jika kita memotong sekali lagi, kita pasti bisa memotong dengan melewati setiap garis potongan yang pernah dilakukan sebelumnya. Karena kita melewati X-1 bekas pemotongan, kita menghasilkan X buah potongan yang baru.
Dari observasi tersebut, kita dapat merancang rumus rekursif untuk jawaban atas pertanyaan di atas. Misalkan f(x) menyatakan banyaknya potongan kue maksimum jika dilakukan x kali pemotongan. Didapat:

f (0) = 1

$f(0) = 1$ , hanya ada 1 potong kue jika tidak dilakukan pemotongan sama sekali

f (x) = f (x - 1) + x

$f(x) = f(x-1) + x$
Dalam bentuk bukan rekursif:

f (x) = 1 + 1 + 2 + 3 + . . . + x

$f(x) = 1 + 1 + 2 + 3 + ... + x$
atau

f (x) = 1 + \frac{x (x + 1)}{2}

$f(x) = 1 + \frac{x(x+1)}{2}$
Sehingga banyaknya node maksimalnya adalah

O (N^{2})

$O(N^2)$

Sekarang kita kembali lagi ke soal. Kapan 3 buah node (sebut saja u, v, dan w) menjadi sebuah segitiga sesuai yang diinginkan soal? Hal ini terjadi jika terdapat edge yang menghubungkan (u, v), (u, w), dan (v, w). Jadi kita tinggal pilih suatu node, lalu cek untuk setiap pasangan tetangganya apakah mereka terhubung. Jika ya, tambahkan jawaban akhir dengan 1. Di akhir, bagi jawaban dengan 3 karena satu segitiga akan dihitung 3 kali. Berhubung suatu titik tidak mungkin menjadi titik persekutuan dari 3 atau lebih garis, maka setiap node hanya akan memiliki maksimal 4 tetangga. Jadi jika grafnya sudah dibangun, menghitung banyaknya segitiga dapat dilakukan dalam $O(N^2)$

Sekarang masalahnya tinggal bagaimana cara membangun graf tersebut. Pastinya anda membutuhkan cara untuk mencari titik potong sepasang segmen garis. Selain itu, anda juga mungkin membutuhkan cara untuk memeriksa apakah suatu titik berapa di suatu segmen garis. Segala yang dibutuhkan untuk menjawab pertanyaan tersebut adalah ilmu tentang vektor dalam geometri, terutama cross product. Saya tidak membahas bagaimana cara mencari titik potong antar segmen garis atau memeriksa titik ada di suatu garis. Anda harus mencari tahu sendiri.

Membangun graf dari masukan yang diberikan dapat dilakukan dalam $O(N^2)$ , sehingga kompleksitas solusi adalah $O(N^2)$ . Cukup untuk mendapatkan accepted. Berikut kode saya:

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <set>
  
#define REP(a,b) for (int a=0; a<b; a++)
#define FORU(a,b,c) for (int a=b; a<=c; a++)
#define FORD(a,b,c) for (int a=b; a>=c; a--)
#define RESET(a,b) memset(a, b, sizeof a)
  
#define LOLO long long
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define PII pair<int,int> 
#define PDD pair<double,double> 
#define EPS 1e-8
  
#define __ puts("")
  
#define x FI
#define y SE
#define xa FI.FI
#define xb SE.FI
#define ya FI.SE
#define yb SE.SE
  
using namespace std;
  
vector<int> mmi[610],adlis[150000];
set<pii> him;
PDD tik[150000];
pair<PII,PII> grs[610];
int n,m,h1,h2,h3,h4,tot;
int a1,a2,b1,b2,p;
LOLO da1,da2,db1,db2,dc1,dc2;
  
PII konv(int a, int b){
    int c,d;
      
    if ((a == 0) || (a == 2)){
        c = b;
    }else if (a == 1){  
        c = m;
    }else{
        c = 0;
    }
      
    if ((a == 1) || (a == 3)){
        d = b;
    }else if (a == 2){  
        d = m;
    }else{
        d = 0;
    }
      
    return MP(c,d);
}   
  
int det(PII a, PII b, PII c){
    da1 = a.x;
    da2 = a.y;
    db1 = b.x;
    db2 = b.y;
    dc1 = c.x;
    dc2 = c.y;
      
    LOLO h = (da1*db2) + (db1*dc2) + (dc1*da2) 
           - (da1*dc2) - (db1*da2) - (dc1*db2);
             
    if (h < 0) return -1;
    if (h > 0) return 1;
    return 0;
}   
  
bool insec(pair<PII,PII> a, pair<PII,PII> b){
    h1 = det(a.FI, a.SE, b.FI);
    h2 = det(a.FI, a.SE, b.SE);
    h3 = det(b.FI, b.SE, a.FI);
    h4 = det(b.FI, b.SE, a.SE);
      
    if ((h1*h2 <= 0) && (h3*h4 <= 0) && !((h1==0) && (h2==0) && (h3==0) && (h4==0))){
        return 1;
    }
    return 0;
}   
  
double crosp(double a, double b, double c, double d){
    return (a*d) - (b*c);
}   
  
PDD getsec(pair<PII,PII> a, pair<PII,PII> b){
    double h1,h2,le;
    double adx,ady;
    double bdx,bdy;
      
    bdx = b.xb - b.xa;
    bdy = b.yb - b.ya;
    le = sqrt(bdx*bdx + bdy*bdy);
      
    adx = a.xa - b.xa;
    ady = a.ya - b.ya;
    h1 = fabs(crosp(adx,ady,bdx,bdy)/le);
      
    adx = a.xb - b.xa;
    ady = a.yb - b.ya;
    h2 = h1 + fabs(crosp(adx,ady,bdx,bdy)/le);  
      
    double px,py;
    px = a.xa + (h1/h2)*(a.xb - a.xa);
    py = a.ya + (h1/h2)*(a.yb - a.ya);
      
    return MP(px,py);
}
  
bool kom(int a, int b){
    if (fabs(tik[a].x - tik[b].x) > EPS){
        return tik[a].x < tik[b].x;
    }else{
        return tik[a].y < tik[b].y;
    }
}   
  
int main(){
    scanf("%d%d", &m, &n);
    REP(i,n){
        scanf("%d%d%d%d", &a1, &a2, &b1, &b2);
          
        grs[i].FI = konv(a1,a2);
        grs[i].SE = konv(b1,b2);
    }
      
    grs[n++] = MP(MP(0,0),MP(0,m));
    grs[n++] = MP(MP(0,m),MP(m,m));
    grs[n++] = MP(MP(m,m),MP(m,0));
    grs[n++] = MP(MP(m,0),MP(0,0));
      
    p=0;
    REP(i,n){
        FORU(j,i+1,n-1){
            if (insec(grs[i],grs[j])){
                tik[p] = getsec(grs[i],grs[j]);
                      
                mmi[i].PB(p);
                mmi[j].PB(p);
                p++;
            }
        }
    }   
      
    REP(i,n){
        sort(mmi[i].begin(), mmi[i].end(), kom);    
          
        FORU(j,0,(int)mmi[i].size()-2){
            adlis[mmi[i][j]].PB(mmi[i][j+1]);
            adlis[mmi[i][j+1]].PB(mmi[i][j]);
              
            him.insert(MP(mmi[i][j],mmi[i][j+1]));
            him.insert(MP(mmi[i][j+1],mmi[i][j]));
        }
    }
 
    tot=0;
    REP(i,p){   
        REP(j,adlis[i].size()){
            FORU(k,j+1,(int)adlis[i].size()-1){
                if (him.count(MP(adlis[i][j], adlis[i][k]))){
                    tot++;
                }
            }
        }
    }
      
    printf("%d\n", tot/3);
      
   return 0;  
}

Pages

Sabtu, 09 Februari 2013

tokilearning - Webs

Tidak ada komentar :

Posting Komentar

Pages

Sabtu, 09 Februari 2013

tokilearning - Webs

Tulisan terkait:

Tidak ada komentar :

Posting Komentar